409157: GYM103447 I Power and Zero
Description
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.
InputThe 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$$$.
OutputFor each test case:
Output one line containing one integer, denoting the answer.
ExampleInput3 5 1 2 3 4 5 2 1 4 1 7Output
3 3 1Note
For the first sample case, one possible scheme:
- Appoint $$$B = \{1, 3, 5\}$$$, then $$$A$$$ will be $$$\{0, 2, 1, 4, 1\}$$$.
- Appoint $$$B = \{3, 2, 4\}$$$, then $$$A$$$ will be $$$\{0, 0, 0, 0, 1\}$$$.
- Appoint $$$B = \{5\}$$$, then $$$A$$$ will be $$$\{0, 0, 0, 0, 0\}$$$.
For the second sample case, one possible scheme:
- Appoint $$$B = \{1, 2\}$$$, then $$$A$$$ will be $$$\{0, 2\}$$$.
- Appoint $$$B = \{2\}$$$, then $$$A$$$ will be $$$\{0, 1\}$$$.
- Appoint $$$B = \{2\}$$$, then $$$A$$$ will be $$$\{0, 0\}$$$.
For the third sample case, one possible scheme:
- Appoint $$$B = \{1, 1, 1\}$$$, then $$$A$$$ will be $$$\{0\}$$$.