题目描述

Jane 是多种音乐的忠实粉丝。但他不仅喜欢听音乐，还喜欢创作音乐。他最喜欢电子音乐，所以他创建了自己的音符系统，在他看来，这是最适合电子音乐的系统。

由于 Jane 也喜欢信息学，因此在他的系统中，音符用整数 $2^k$ 表示，其中 $k \ge 1$ 是一个正整数。但是，如你所知，你不能仅使用单个音符来创作音乐，因此 Jane 使用两个音符的组合。两个音符 $(a,b)$ 的组合（其中 $a=2^k$ 且 $b=2^l$），他用整数 $a^b$ 来表示。

例如，如果 $a=8=2^3$，$b=4=2^2$，则组合 $(a,b)$ 的值由整数 $a^b=8^4=4096$ 表示。请注意，不同的组合可以具有相同的值，例如，组合 $(64,2)$ 也由整数 $64^2=4096$ 表示。

Jane 已经选择了他想要在新旋律中使用的 $n$ 个音符。然而，由于它们对应的值可能非常大，所以他将它们写为长度为 $n$ 的数组 $a$，那么第 $i$ 个音符就是 $b_i=2^{a_i}$。数组 $a$ 中的整数可以重复。

旋律将由两个音符的几种组合组成。Jane 想知道有多少对音符 $b_i, b_j$ ($i < j$) 使得组合 $(b_i, b_j)$ 的值等于组合 $(b_j, b_i)$ 的值。换句话说，他想要计算满足 $b_i^{b_j} = b_j^{b_i}$ 的数对 $(i,j)$ ($i < j$) 的数量。

请帮助他找出满足该条件的数对的数量。

输入

第一行包含一个整数 $t$ ($1 \le t \le 10^4$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$) — 数组的长度。

下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — 数组 $a$。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出满足给定条件的数对的数量。

样例

输入样例

5
1
2
4
3 1 3 2
2
1000 1000
3
1 1 1
19
2 4 1 6 2 8 5 4 2 10 5 10 8 7 4 3 2 6 10

输出样例

0
2
1
3
19

限制

每次测试时间限制: 1 秒
每个测试的内存限制: 256 MB
输入: 标准输入
输出: 标准输出