题目描述

下面看一个比较简单的递归函数：

\(f(0)=0\)

\(f(2×x)=f(x)\)

\(f(2×x+1)=f(x)+1\)

现在输入 \(n\) 个数 \(a_i\)，编程统计一共有多少对数字的函数值相同，即如果有 \(i≠j\)，而 \(f(a_i)=f(a_j)\)，则 \((i,j)\) 算成是符合条件的一对数字，当然 \((i,j)\) 和 \((j,i)\) 不需要重复计算。

格式

输入格式

第一行为正整数 \(t(≤5)\)，表示数据组数；每组数据中，第一行为正整数 \(n(≤ 10^5)\)，接下来一行为以空格隔开的 \(n\) 个正整数 \(a (≤10^9)\)。

输出格式

对于每组数据，输出函数值相同的数对数目。

样例1

输入样例1

1
3
1 2 4

输出样例1

3

样例解释

\(f(1)=f(2)=f(4)=1\)，即 \((1,2)(1,4)(2,4)\) 是符合条件的数对，所以答案是 \(3\)。

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T1\)

文件IO

freopen("pairs.in","r",stdin);
freopen("pairs.out","w",stdout);