Rakesh has an array A having N positive integers. He wants to select indices i and j ( 1≤i<j≤N ) such that the maximum power of 2 that divides A[i]×A[j] is at max 1 . In how many ways can he do this ?
INPUT:
First line contains integer N, which denotes size of the array.
Second line contains N space separated integers, i.e the elements of A.
CONSTRAINTS:
1≤N≤1051≤A[i]≤109
OUTPUT:
The required answer in one line.
The possible pairs of elements he can select are (3,2), (5,2) and (3,5) since the maximum power of 2 that divides 3x2=6 is 1, 5x2=10 is 1, and 3x5=15 is 0 .