Little Gopu likes to play very much. As you know he only plays with numbers. So he is given n numbers. Now he tries to group the numbers into collections where each collection contains exactly two numbers. He can form the collection of two numbers a and b (a <= b), if and only if b is either 2 * a or 2 * a + 1.

Note that you can not use a single number in forming of more than one collections. Eg. 1, 2, 4 He can divide the numbers into a single collection only either [1, 2] or [2, 4] because each collection requires exactly two numbers, and each number has to be used only once in a group.

Given n numbers, Find out how many maximum number of collections he can form ?

Input

T: number of test cases.

For each test case, First line will contain n :  (1 <= n <= 10^5)

Then next line will contain n numbers single space separated. Range of each number will be between 1 and 10^18.

Sum of n over all the tests will be at most 10^6. So number of test cases are decided on this criteria.

Output

For each test case, output maximum number of collections that can be formed.

Example

Input:
4
2
1 2
3 
1 2 4
4
1 2 4 8
2
4 4 

Output:
1
1
2
0