You are given an array ARR having N integers. Your task is to find the sum of Hamming Distance for each pair of the array elements.

Hamming Distance for two given integers 'A' and 'B' is defined as the minimum number of bits that needs to be toggled to make both the integers equal.

For example:

Consider A=4 and B=7
Binary representation of 4 = 100
Binary representation of 7 = 111
For the given example, if we flip the values of the last two least significant bits of A to 1 then A will become 7. As we can change the value of A to B by 2 flips. Therefore the Hamming Distance, in this case, is 2.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the number of elements in the array.

The second line of each test contains 'N' space-separated integers denoting the array elements.

Output Format:

For each test case, return the sum of Hamming Distance for all the pairs.

Note:

You are not required to print anything just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^4
0 <= ARR[i] <=10^9

Time limit: 1 second