Counting Set Bits for Minimum Operations

You are given multiple test cases. In each test case, you are provided with an integer \(N\) and an array of \(N\) non-negative integers. For each integer, you must count the number of set bits (i.e. the number of 1s in their binary representation). The minimum number of operations required to reduce all the numbers to zero is defined as the sum of these counts over the entire array.

In other words, for an integer \(x\), let \(f(x)\) denote the number of set bits in its binary representation. Then, for an array \(A\) with \(N\) elements, the answer is given by:

[ \text{answer} = \sum_{i=1}^{N} f(A_i) \quad \text{where} \quad f(x) = #{i : \text{the } i\text{-th bit of } x \text{ is } 1}. ]

You need to read the input from standard input and write the output to standard output.

inputFormat

The first line contains a single integer \(T\), the number of test cases.

For each test case, the first line contains a single integer \(N\) representing the number of elements in the array. The next line contains \(N\) space-separated non-negative integers.

outputFormat

For each test case, print the minimum number of operations required (i.e. the sum of the set bits for each number) on a new line.

## sample

3
3
5 7 12
4
8 4 2 1
2
1 6

7
4
3

</p>