IITKWPCO - Create Collections


  Little Feluda likes to play very much. As you know he only plays with numbers. So he is given n numbers. Now tries to group the numbers into disjoint collections each containing two numbers. He can form the collection containing two numbers iff small number in the collection is exactly half of large number.

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

Input

T: number of test cases. (1 <= T <= 100).

For each test case:

First line will contain n :  (1 <= n <= 100)

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

Output

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

Example

Input:
2
2
1 2
3
1 2 4
Output:
1
1

hide comments
$iddharth prasad: 2014-06-30 21:11:40

AC in first attempt but this problem teach me lot!

JIMMY KUMAR: 2014-06-30 21:11:40

accepted in 1 go :)

Last edit: 2013-08-29 19:34:42
Amit Shekhar: 2014-06-30 21:11:40

i am getting right ans for all above test cases still WA , Please provide some more test cases

abhishek arora: 2014-06-30 21:11:40

finally AC :)
@NP- thanx..

aman kumar jha: 2014-06-30 21:11:40

30 hrs , 10 WAs :( . finally ac. :)

abhishek arora: 2014-06-30 21:11:40

pls provide some test case... i m getting WA...

[Lakshman]: 2014-06-30 21:11:40

@p@nw@r try with large inputs with max test cases.use multiplication instead of division, if you are doing somewhere

p@nw@r: 2014-06-30 21:11:40

@Lakshman i'm getting the right answer ,for these test cases...

shinchan: 2014-06-30 21:11:40

i m getting WA...can anyone provide me some critical test cases..

Last edit: 2013-08-26 14:50:01
[Lakshman]: 2014-06-30 21:11:40

@Aman kumar jha Yes.


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