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

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

hide comments
2015-01-24 23:47:37 Anmol Pandey
To those getting WA or Runtime Error
1)range is not in 10^6 it is around 10^7
2)try changing cin to scanf
there isn't any trick involved.
2015-01-17 08:32:58 MoHiB
After lot of wa due to silly mistakes got ac... :)
2015-01-16 11:14:16 Abhay Pratap
Passing test cases and even all the cases given in comments...still WA!!
Anyone with special case??help..
2015-01-16 10:57:53 ash_cash
damn easy... cool!!! :) :)
ac in 1 go hurray!!!

Last edit: 2015-01-16 10:58:13
2014-08-18 10:16:30 ||N0VICE||
No need to think too
much my n^2 soln got AC in 0.0s

Last edit: 2014-08-18 10:17:13
2014-08-17 07:27:17 Akshay Kamthan
wooh! AC in one go for the second time ;):P
2014-08-15 18:16:32 Naruto uzumaki
DIVISION might lead to confusion . 15/2 =7 and 14/2=7
2014-06-30 21:11:40 Diksha Jaiswal
AC in 1st attempt...5 mins code :D
2014-06-30 21:11:40 sarelfeniel
Very easy... plus it's on Cube so insanely fast!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.