CF1899D Yarik and Musical Notes

Yarik 是各种音乐的忠实粉丝。但 Yarik 不仅喜欢听音乐，还喜欢创作音乐。他最喜欢电子音乐，因此他为电子音乐创造了一套属于自己的音符系统，在他看来，这套系统最适合电子音乐。 由于 Yarik 也喜欢信息学，在他的系统中，音符用 $2^k$ 表示，其中 $k \ge 1$，为正整数。但如你所知，光用音符还不能写出音乐，因此 Yarik 使用两个音符的组合。两个音符 $(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)$ 也用整数 $4096 = 64^2$ 表示。 Yarik 已经选好了 $n$ 个他想在新旋律中使用的音符。由于这些整数可能非常大，他将它们记录为长度为 $n$ 的数组 $a$，第 $i$ 个音符为 $b_i = 2^{a_i}$。数组 $a$ 中的整数可能重复。 旋律将由若干对音符的组合组成。Yarik 想知道，有多少对音符 $b_i, b_j$（$i < j$）满足组合 $(b_i, b_j)$ 与组合 $(b_j, b_i)$ 相等。换句话说，他想统计有多少对 $(i, j)$（$i < j$）满足 $b_i^{b_j} = b_j^{b_i}$。请你帮他计算满足条件的对数。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示数组的长度。 接下来一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），表示数组 $a$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

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

由 ChatGPT 4.1 翻译