409157: GYM103447 I Power and Zero

Given a sequence $$$A_1, A_2, \cdots, A_n$$$ whose elements are all positive integers. You should do some operations to make the sequence all zero. For each operation, you can appoint a sequence $$$B_1, B_2, \cdots, B_m \,(B_i \in \{1, 2, \cdots, n\})$$$ of arbitrary length $$$m$$$ and reduce $$$A_{B_i}$$$ by $$$2^{i-1}$$$ respectively. Specially, one element in the given sequence can be reduced multiple times in one operation. Determine the minimum possible number of operations to make the given sequence all zero.

The first line contains one integer $$$T\,(1\le T \le 1000)$$$, denoting the number of test cases.

For each test case:

The first line contains one integer $$$n\,(1\le n \le 10^5)$$$, denoting the length of given sequence.

The second line contains $$$n$$$ integers $$$A_1, A_2, \cdots, A_n \, (1\le A_i \le 10^9)$$$, denoting the given sequence.

It is guaranteed that $$$\sum n \le 10^5$$$.

For each test case:

Output one line containing one integer, denoting the answer.

3
5
1 2 3 4 5
2
1 4
1
7

3
3
1

For the first sample case, one possible scheme:

1. Appoint $$$B = \{1, 3, 5\}$$$, then $$$A$$$ will be $$$\{0, 2, 1, 4, 1\}$$$.
2. Appoint $$$B = \{3, 2, 4\}$$$, then $$$A$$$ will be $$$\{0, 0, 0, 0, 1\}$$$.
3. Appoint $$$B = \{5\}$$$, then $$$A$$$ will be $$$\{0, 0, 0, 0, 0\}$$$.

For the second sample case, one possible scheme:

1. Appoint $$$B = \{1, 2\}$$$, then $$$A$$$ will be $$$\{0, 2\}$$$.
2. Appoint $$$B = \{2\}$$$, then $$$A$$$ will be $$$\{0, 1\}$$$.
3. Appoint $$$B = \{2\}$$$, then $$$A$$$ will be $$$\{0, 0\}$$$.

For the third sample case, one possible scheme:

1. Appoint $$$B = \{1, 1, 1\}$$$, then $$$A$$$ will be $$$\{0\}$$$.