Question
Stick Pair Divisor Count
In a crafty village, Ravi discovered N sticks, each with a unique length denoted by Aᵢ. He learned that each stick could be shortened to any length Y as long as Aᵢ % Y == 0. This meant that a stick of length Aᵢ could be burnt to X different lengths, where X is the count of divisors of Aᵢ. Curious about the sticks, Ravi decided to find the total number of unordered pairs of sticks that had the same X value. Can you help Ravi determine the number of such pairs?
Input
The first line of the input contains a single integer N.
The second line of the input contains N space-separated integers.
Constraints
1 ≤ N ≤ 105
1 ≤ Ai ≤ 106
The second line of the input contains N space-separated integers.
Constraints
1 ≤ N ≤ 105
1 ≤ Ai ≤ 106
Output
Print the total number of unordered pair of sticks whose X value is the same.
Example
Sample Input
3
4 9 2
Sample Output
1
Explanation
Sticks of length 4 and 9 both have X value = 3.
3
4 9 2
Sample Output
1
Explanation
Sticks of length 4 and 9 both have X value = 3.