All Submissions


The ACM body loves fiddling with number sequences. Now we've got a sequence a1,a2,...,an, consisting of n positive integers. Also, we have a function f(x), which can be defined with the following recurrence:

f(0)=0;
f(2·x)=f(x);
f(2·x+1)=f(x)+1.

The body now wonders, how many pairs of indexes (i,j) (1<= i < j <= n) are there, such that f(ai) = f(aj). The ACM approaches you , being an awesome problem solver , to help us count the number of such pairs.

Input
The first line contains T, the number of test cases . Each test case contains two lines. The first line contains integer n (1<=n<=103). The second line contains n positive integers a1,a2,...,an (1<=ai<=109).

The numbers in the lines are separated by single spaces.

Output
In a single line print the answer to the problem.


SAMPLE :

INPUT :

2

3
1 2 4

3
5 3 1

OUTPUT:
3
1

Note:
In the first sample any pair (i,j) will do, so the answer is 3.

In the second sample only pair (1,2) will do.

Problem Setter : Akshit Poddar
Problem Tester : Shikhar Sharad

Languages: Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0