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 \lt 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 \lt j \leq n$$$ such that $$$p_i \cdot p_j$$$ is divisible by $$$i \cdot j$$$ without remainder.

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.

Permutation Problem (Hard Version)

Examples