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 ≤ 105)

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

Sum of n over all the tests will be at most 106. 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