B'This is the hard version of the problem. The only difference is that in this version n <= q 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 <= q i < j <= q 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. Each test consists of several sets of input data. The first line contains a single integer t ( 1 <= q t <= q 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 <= q n <= q 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 <= q p_i <= q 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 . For each set of input data, output the number of index pairs 1 <= q i < j <= q n such that p_i cdot p_j is divisible by i cdot j without remainder. 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. '...