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 separated. 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

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

hide comments
2014-06-30 21:11:40 aman kumar jha
@praveen123 are numbers integers? plz specify..
2014-06-30 21:11:40 salvager
still WA any critical case


Last edit: 2013-08-26 10:47:49
2014-06-30 21:11:40 The Mundane Programmer
getting 6 for above test case , still wa. :(


Last edit: 2013-08-25 17:24:45
2014-06-30 21:11:40 [Lakshman]
@Fussy test cases are correct.
we can make pair either of (1,2) or (2,4) hens ans is 1.
2014-06-30 21:11:40 p@nw@r
two WA..plz provide more test cases.....
2014-06-30 21:11:40 Fussy
ans for 2nd case shud be 2-(1,2),(2,4) ???
how come 1 pls ans ????
2014-06-30 21:11:40 [Lakshman]
Easy one...
2014-06-30 21:11:40 Lakshay Singhal
damm too simple...AC in first attempt
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.