CF2269B.KiaKio and Squared Numbers

Kia and Kio spent the summer at the port of Mehragan, where $n$ lighthouses stand on the cliffs facing the dark sea.

The lighthouses of Mehragan do not give light. Every night a number is written in fire on each of them, and the sailors read their way from those numbers.

The law of the lighthouses is this: if a lighthouse shows $x$ tonight, then tomorrow night it shows the sum of the squares of the decimal digits of $x$.

For example, a lighthouse showing $23$ will show $2^2+3^2=13$ tomorrow, then $1^2+3^2=10$, and then $1$.

On night $0$ of the season, lighthouse $i$ shows the number $a_i$. From that night on, the law is applied once every night, forever.

Kio calls two lighthouses $i$ and $j$ in tune if there exists a night after which, forever, both of them show exactly the same number on every single night.

Kia asks: how many pairs $(i, j)$ with $i \lt j$ are in tune?

基亚和基奥在梅赫拉甘港度过了夏天，那里有 $n$ 座灯塔矗立在面向幽暗大海的悬崖上。

梅赫拉甘的灯塔并不发光。每晚，每座灯塔都会用火焰写出一个数字，水手们便依靠这些数字辨明航向。

灯塔的运行法则如下：若某座灯塔今晚显示数字 $x$，则明晚它将显示 $x$ 的十进制各位数字的平方和。

例如，一座今晚显示 $23$ 的灯塔，明晚会显示 $2^2+3^2=13$，再下一天显示 $1^2+3^2=10$，接着显示 $1$。

在本季第 $0$ 夜，第 $i$ 座灯塔显示数字 $a_i$。从该夜起，上述法则每夜执行一次，并永远持续下去。

基奥将两座灯塔 $i$ 和 $j$ 称为“和谐的”，当且仅当存在某个夜晚，从此之后，在每一个夜晚，这两座灯塔都恰好显示完全相同的数字。

基亚提问：满足 $i \lt j$ 的和谐灯塔对 $(i, j)$ 共有多少对？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

Each test case consists of two lines.

The first line of each test case contains a single integer $n$ ($1 \le n \le 1000$) — the number of lighthouses.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the number shown by each lighthouse on night $0$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print a single integer — the number of pairs $(i, j)$ with $i \lt j$ such that lighthouses $i$ and $j$ are in tune.

对于每个测试用例，输出一个整数——满足 $i \lt j$ 且灯塔 $i$ 与灯塔 $j$ 处于调谐状态的数对 $(i, j)$ 的个数。

In the first test case:

• Lighthouse $1$ starts at $7$: $7 \to 49 \to 97 \to 130 \to 10 \to 1$, and it stays at $1$ forever.
• Lighthouses $2$ and $4$ both start at $4$, so they show the same number on every night.
• Lighthouse $3$ starts at $16$ and lighthouse $5$ starts at $2$; each of them is at a different point of the cycle Kio found, and never matches anybody.

So the only pair in tune is $(2, 4)$, and the answer is $1$.

In the second test case, every lighthouse sooner or later reaches $1$ and stays there, so all of them are pairwise in tune, which gives $6$ pairs.

In the fourth test case, on night $1$, lighthouse $2$ shows $2^2+0^2 = 4$, and lighthouse $1$ shows $2^2 = 4$. From night $1$ on, they are identical forever. Lighthouse $3$ starts at $4$, so it is one night ahead of both of them and is in tune with neither.

在第一个测试用例中：

• 灯塔 $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$，因此比它们领先一个夜晚，与二者均不同步。