I. Power and Zero
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Output

For each test case:

Output one line containing one integer, denoting the answer.

Example
Input
3
5
1 2 3 4 5
2
1 4
1
7
Output
3
3
1
Note

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\}$$$.