CF2269B KiaKio and Squared Numbers

Kia 和 Kio 在 Mehragan 港度过了整个夏天，那里有 $n$ 座灯塔矗立在悬崖上，面对着漆黑的大海。 Mehragan 的灯塔并不会发光。每天夜里，每座灯塔上都会用火焰写下一个数字，水手们便靠读这些数字来辨别方向。 灯塔的法则如下：如果一座灯塔今晚显示 $x$，那么明天夜里它显示 $x$ 的十进制各位数字的平方和。 例如，一座显示 $23$ 的灯塔，明天会显示 $2^2+3^2=13$，之后是 $1^2+3^2=10$，再之后是 $1$。 在这个季节的第 $0$ 夜，第 $i$ 座灯塔显示数字 $a_i$。从那一夜起，法则每夜执行一次，永不停息。 如果存在某一夜之后，两座灯塔 $i$ 和 $j$ 在之后的每一个夜晚都恰好显示相同的数字，Kio 就称它们是**合拍**（in tune）的。 Kia 想知道：有多少对 $(i, j)$（满足 $i < j$）是合拍的？

每个测试文件包含多组测试数据。第一行包含测试数据组数 $t$（$1 \le t \le 1000$）。接下来依次描述每组测试数据。 每组测试数据由两行组成。 第一行包含一个整数 $n$（$1 \le n \le 1000$）——灯塔的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）——每座灯塔在第 $0$ 夜显示的数字。 保证所有测试数据的 $n$ 之和不超过 $1000$。

对于每组测试数据，输出一行一个整数——满足 $i < j$ 且灯塔 $i$ 与灯塔 $j$ 合拍的无序对 $(i, j)$ 的数量。

在第一组测试数据中： - 灯塔 $1$ 从 $7$ 出发：$7 \to 49 \to 97 \to 130 \to 10 \to 1$，此后永远停留在 $1$。 - 灯塔 $2$ 和灯塔 $4$ 都从 $4$ 出发，因此它们在每一夜都显示相同的数字。 - 灯塔 $3$ 从 $16$ 出发，灯塔 $5$ 从 $2$ 出发；它们各自处在 Kio 所发现的循环中的不同位置，永远不会与任何灯塔相同。 所以唯一合拍的一对是 $(2, 4)$，答案为 $1$。 在第二组测试数据中，每座灯塔或早或晚都会到达 $1$ 并停留在那里，因此它们两两合拍，共有 $6$ 对。 在第四组测试数据中，在第 $1$ 夜，灯塔 $2$ 显示 $2^2+0^2 = 4$，灯塔 $1$ 显示 $2^2 = 4$。从第 $1$ 夜起，它们永远完全相同。灯塔 $3$ 从 $4$ 出发，因此它比这两座灯塔超前一夜，与它们都不合拍。 由 deepseek v4.1-flash 翻译。