D. How Long Until Nothing Remains?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Before her final sortie, Chtholly asks Willem three questions.

The first is this: if the end is inevitable, how long will it take until nothing remains?

Willem cannot answer her directly. Instead, he writes down $$$n$$$ positive integers $$$a_1,a_2,\ldots,a_n$$$.

Each operation takes one second. In one operation, Willem does the following:

  • Choose an index $$$p$$$ ($$$1\le p\le n$$$);
  • Then, replace $$$a_p$$$ with $$$\left\lfloor\dfrac{a_p}{2}\right\rfloor$$$, and for every $$$i\ne p$$$, replace $$$a_i$$$ by $$$\left\lceil\dfrac{a_i}{2}\right\rceil$$$. All replacements are performed simultaneously.

Find the minimum number of seconds needed to make all $$$n$$$ integers equal to $$$0$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$1\le n\le2\cdot10^5$$$) — the number of integers.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le10^9$$$) — the initial integers.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output

For each test case, output a single integer — the minimum number of seconds needed to make all integers equal to $$$0$$$.

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

In the first test case, the only integer changes as $$$3\to1\to0$$$, so the answer is $$$2$$$.

In the second test case, an integer equal to $$$1$$$ becomes $$$0$$$ only when its index is chosen. Thus, at least $$$3$$$ seconds are necessary, and choosing every index once is sufficient.

In the third test case, an optimal sequence is:

  1. Choose $$$p=1$$$: $$$[1,2,4]\to[0,1,2]$$$;
  2. Choose $$$p=2$$$: $$$[0,1,2]\to[0,0,1]$$$;
  3. Choose $$$p=3$$$: $$$[0,0,1]\to[0,0,0]$$$.

In the fourth test case, an optimal sequence is $$$[5,2]\to[2,1]\to[1,0]\to[0,0]$$$, where the chosen indices are $$$1$$$, $$$2$$$, and $$$1$$$.