G2. 排列问题（困难版）

时间限制：3 秒
内存限制：128 兆字节

这是该问题的困难版本。唯一的区别在于，在此版本中 $n \le 5 \cdot 10^5$ 且所有输入数据的 $n$ 之和不超过 $5 \cdot 10^5$ 。

给定一个长度为 $n$ 的排列 $p$ 。计算满足以下条件的下标对 $1 \le i < j \le n$ 的个数： $p_i \cdot p_j$ 能被 $i \cdot j$ 整除。

排列是一个由 $n$ 个整数组成的序列，其中 $1$ 到 $n$ 的每个整数恰好出现一次。例如， $[1]$ 、 $[3,5,2,1,4]$ 、 $[1,3,2]$ 是排列，而 $[2,3,2]$ 、 $[4,3,1]$ 、 $[0]$ 不是。

输入

每个测试包含多组输入数据。第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ）——输入数据的组数。接下来是各组数据的描述。

每组数据的第一行包含一个整数 $n$ （ $1 \le n \le 5 \cdot 10^5$ ）——排列 $p$ 的长度。

第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \dots, p_n$ （ $1 \le p_i \le n$ ）——排列 $p$ 。

保证所有输入数据的 $n$ 之和不超过 $5 \cdot 10^5$ 。

对于每组输入数据，输出满足条件 $p_i \cdot p_j$ 能被 $i \cdot j$ 整除的下标对 $i < j$ 的个数。

6
1
1
2
1 2
3
2 3 1
5
2 4 1 3 5
12
8 9 7 12 1 10 6 3 2 4 11 5
15
1 2 4 6 8 10 12 14 3 9 15 5 7 11 13

在第一组输入数据中，没有下标对，因为排列长度为 $1$ 。

在第二组输入数据中，有一个下标对 $(1,2)$ 且它满足条件。

在第三组输入数据中，下标对 $(1,2)$ 满足条件。

在第四组输入数据中，满足条件的下标对为 $(1,2)$ 、 $(1,5)$ 和 $(2,5)$ 。