Submit Best Submissions All Submissions

182. Rami and Squares


Problem Statement:
Rami's birthday is today. He had so many gifts for his birthday, but one gift in particular he is very curious about.

He opened the gift and found N sticks, each with length ai . Now he is wondering how many squares can he make with these sticks. He wants his squares to be perfect, so he can't break any stick, neither can he put two sticks together in one square edge.


Input Format:
The first line of input has one integer T, which is the number of test cases. Next are T test cases.

Each test case starts with and integer N, the number of sticks Rami has. Followed by N integers a1, a2 ... an representing the side lengths of the N sticks.

( 1 ≤ N ≤ 100,000 )

( 1 ≤ ai ≤ 109 )


Output Format:
For each test case print a single number to the output, the number of squares Rami can put together.


Sample Input:
3 7 1 1 2 2 1 1 2 14 3 1 4 4 4 7 7 7 7 7 7 7 7 7 9 1 1 1 3 3 3 5 5 5


Sample Output:
1 2 0


Notes:
In the first test case, Rami can make one square with the four 1 sticks.

In the second test case, Rami can make two squares with side length = 7, note that he can't have a square with side length=4 because he can't combine 3+1 into one side.

Sometimes Rami can't make any squares!





Added by: samiemad
Added at: 2014-07-26 09:00:14 UTC
Time Limit: 1 second
Partial score: No
Source:Practical C++ and Algorithms Course, Level 1, By. Sami EMAD