Pairwise Sum of Hamming Distance

Given an array ARR containing N integers, your task is to calculate the total sum of the Hamming Distance for all possible pairs of elements in the array.

Hamming Distance

The Hamming Distance between two integers A and B is the number of bits that need to be toggled (changed) in either A or B to make them equal.

Example:

Explanation:

Consider A = 4 and B = 7
Binary representation of 4 = 100
Binary representation of 7 = 111
To convert A to B, flip the last two least significant bits of A to 1.
In this case, you need 2 flips.
Therefore, the Hamming Distance between A and B is 2.

Input:

The first line of input contains an integer T, the number of test cases.
The first line of each test case contains an integer N, the number of elements in the array.
The second line of each test case contains N space-separated integers, representing the array elements.

Output:

For each test case, return the total sum of Hamming Distances for all pairs in the array.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10^4
• 0 <= ARR[i] <= 10^9
• Time limit: 1 second

Note:

You are not required to print anything. Just implement the given function to compute the answer.