Sphere Online Judge

SPOJ Problem Set (classical)

15627. Create Collections

Problem code: IITKWPCO


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

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

hide comments
2014-03-25 19:28:36 neeraj
woww!!! it means if you are using division your solution would directly rejected!!!! :( :/ finally accepted with same logic but with *
2014-03-17 18:54:43 NISHANT RAJ
simple brute force work here.
try http://www.spoj.com/problems/SPCJ/
2014-03-10 21:55:55 sawan mahajan
AC in first go...:)
check the test case
1
6
2 4 4 4 4 4
output=1
2014-01-28 19:35:57 Ayush Nigam
o(nlogn) and with much optimisation :D:D
2014-01-15 10:24:10 UnrealNinja
Test File is poorly created.
Integers are not single space separated. There may be more than one space between integers in the list.
2013-12-30 14:13:22 கைபுள்ள
don't divide. use multiplication cause 2 WA :(
2013-12-19 20:11:53 Bhavik
ac in 1st attempt:)
nothing new in this problem
2013-12-19 11:28:37 Will Smith
those who getting WA
pls check this case
1
2
1 3
ans should be 0...
2013-10-28 06:20:45 Prakhar Gupta
too easy.... :)
2013-09-07 05:21:27 quick
check this
4
2 4 8 1
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.