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

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