SPCJ - Gopu and Create Collections Part Two

no tags 

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 seperated. Range of each number will be between 1 and 10^18.

Sum of n over all the tests will be atmost 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

hide comments
Arpit Gupta: 2016-09-15 11:44:58

@d14214 @:.Mohib.:
Can you suggest where i might be going wrong.... my logic is simple greedy and all your given testcases i have covered with single logic. But Still giving WA. Help.!!!

Edit: Quite easier than i initially predicted.
Adding a testcase that might help people in similar situation

Input:
2

9
1 1 2 2 3 4 5 6 11

8
1 1 2 2 3 4 5 11

Output:
4
4

Last edit: 2016-09-15 12:41:42
Anant Upadhyay: 2016-01-22 19:37:01

Nice One :)

Ankit: 2015-09-22 11:40:21

nice greedy :)

:.Mohib.:: 2015-06-14 12:30:55

Nice que...!!!
Some test cases that may help:
5
12
1 2 2 3 5 5 4 20 40 23 12 24
8
1 2 3 4 5 8 14 7
4
1 1 1 1
5
5 1 2 3 11
7
12 24 48 12 42 24 12
Ans:
5
4
0
2
2
All the best.... ;)
2

Archit Kapoor: 2015-01-13 12:25:10

I am getting NZEC, but I have tested my code for various test cases and it is running well. I have tested my code on Ideone also, checked for wild conditions as well. Can anyone help?


Added by:praveen123
Date:2013-12-23
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge