G2. Permutation Problem (Hard Version)
time limit per test
3 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The only difference is that in this version $$$n \leq 5 \cdot 10^5$$$ and the sum of $$$n$$$ for all sets of input data does not exceed $$$5 \cdot 10^5$$$.

You are given a permutation $$$p$$$ of length $$$n$$$. Calculate the number of index pairs $$$1 \leq i < j \leq n$$$ such that $$$p_i \cdot p_j$$$ is divisible by $$$i \cdot j$$$ without remainder.

A permutation is a sequence of $$$n$$$ integers, in which each integer from $$$1$$$ to $$$n$$$ occurs exactly once. For example, $$$[1]$$$, $$$[3,5,2,1,4]$$$, $$$[1,3,2]$$$ are permutations, while $$$[2,3,2]$$$, $$$[4,3,1]$$$, $$$[0]$$$ are not.

Input

Each test consists of several sets of input data. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of sets of input data. Then follows their description.

The first line of each set of input data contains a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) — the length of the permutation $$$p$$$.

The second line of each set of input data contains $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — the permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ for all sets of input data does not exceed $$$5 \cdot 10^5$$$.

Output

For each set of input data, output the number of index pairs $$$1 \leq i < j \leq n$$$ such that $$$p_i \cdot p_j$$$ is divisible by $$$i \cdot j$$$ without remainder.

Example
Input
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
Output
0
1
1
3
9
3
Note

In the first set of input data, there are no index pairs, as the size of the permutation is $$$1$$$.

In the second set of input data, there is one index pair $$$(1, 2)$$$ and it is valid.

In the third set of input data, the index pair $$$(1, 2)$$$ is valid.

In the fourth set of input data, the index pairs $$$(1, 2)$$$, $$$(1, 5)$$$, and $$$(2, 5)$$$ are valid.