H. Good Array
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Majed found an array $$$a$$$ consisting of $$$n$$$ integers.

He can do the following operation many (possibly zero) times:

  • Choose two indexes $$$i$$$ and $$$j$$$ such that $$$a_i$$$ is even and perform $$$a_i= \frac {a_i}{2}$$$ and $$$a_j = a_j \cdot 2$$$.

Majed considers an integer $$$x$$$ good if there are at least $$$x$$$ elements in $$$a$$$ which are greater than or equal to $$$x$$$.

Majed wants to determine the maximum possible integer $$$x$$$ that is considered good after performing the operation several (possibly zero) times.

Input

The first line contains one integer $$$t \: (1 \le t \le 10^4)$$$ — the number of test cases.

The first line of each test case consists of a single integer $$$n \: (1 \le n \le 2 \cdot 10^5)$$$.

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

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output the maximum possible integer $$$x$$$ that is considered good after performing the operation several (possibly zero) times.

Example
Input
3
5
1 2 8 3 1
3
1 1 1
5
1 3 5 99 7
Output
3
1
3
Note

Consider the first testcase. Majed can choose $$$i=3$$$ and $$$j=2$$$, making $$$a=[1,4,4,3,1]$$$, which has $$$3$$$ elements greater than or equal to $$$3$$$.