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:
221 23 1 2 4Output:11```

hide comments
 < Previous 1 2 3 4 5 6 Next > shadow10: 2017-08-17 12:06:10 WAs due to the phrase "disjoint collections".I thought duplicate items are not allowed but it is actually meant that no two collection items have same indices .Confusing problem statement. sameer87: 2017-07-22 15:30:37 range in not under 10^6 :p up79: 2017-06-23 22:06:13 so many WA's easy one ! finally AC ! rajat_singhal: 2017-01-25 07:25:00 more test case plz?? vineetpratik: 2016-07-04 12:25:03 just take care of repetition, easy using map :) pvsmpraveen: 2016-06-27 14:16:48 Never forget to .clear() something after each test case ;) mkfeuhrer: 2016-06-21 23:03:55 simple hashing !! AC in 1 go :-) take 10^7 size and use scanf...! gkr007: 2016-06-02 16:30:05 @kp ur test case really helped ;) atulsinha007: 2016-01-31 07:40:11 nice and easy one.. though 2 WA's :( goyal: 2015-07-19 12:39:05 AC:) using maps

 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