Given an Array A of N integer and number X. find out how many pairs exist in the array where A[i]=A[j] for i ≠ J and (i*j) mod X is 0. I and J are 1 index based.

Example: -

5

2 2 2 2 2

6

Ans - 2

7

3 3 3 2 3 2 2

2

Ans - 6

Time Complexity should not be greater than (nlogn). N is range of 10 to power 5.