# Interesting Pairs solution codechef

Given an array AA having NN elements, Chef wonders how many pairs (i,j)(i,j) exists such that 1i<jN1≤i<j≤N, and AiAjAi⋅Aj is divisible by iji⋅j.

Can you help Chef in finding the number of such pairs?

## Interesting Pairs solution codechef

• The first line of input contains a single integer TT, denoting the number of test cases. The description of the TT testcases follows.
• The first line of each test case contains a single integer NN denoting the number of elements in AA.
• The second line of each test case contains NN space separated integers A1,A2,...,ANA1,A2,…,AN.

### Output Format

For each test case, print a single line containing one integer denoting the number of pairs that satisfies the above condition.

### Constraints

• 1T1041≤T≤104
• 2N1052≤N≤105
• 1Ai1051≤Ai≤105
• The sum of NN over all test cases does not exceed 105105

### Sample Input 1

3
3
1 2 3
4
2 3 5 6
5
3 9 14 6 10


### Interesting Pairs solution codechef

3
2
6


# Interesting Pairs solution codechef

Test Case 11: For all possible pairs of {i,j}{i,j}AiAjAi⋅Aj is divisible by iji⋅j.

Test Case 22: The condition holds for the following two pairs of {i,j}{i,j}{1,2}{1,2}{1,4}{1,4}.