题目描述

有 $n$ 个灯塔，在第 $0$ 天晚上，第 $i$ 个灯塔显示的数字为 $a_i$。

从那天起，灯塔的显示规则如下：如果一个灯塔在今晚显示数字 $x$，那么它在明晚显示的数字将是 $x$ 的十进制各位数字的平方和。

例如，一个显示 $23$ 的灯塔在明晚将显示 $2^2+3^2=13$，再下一晚显示 $1^2+3^2=10$，接着是 $1$。

如果存在某个夜晚，使得在这个夜晚及之后的所有夜晚里，灯塔 $i$ 和灯塔 $j$ 显示的数字完全相同，我们就称这两个灯塔是同步的。

请问有多少对 $(i, j)$ 满足 $i < j$ 且灯塔 $i$ 和灯塔 $j$ 是同步的？

输入格式

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$（$1 \le n \le 1000$）—— 灯塔的数量。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 每个灯塔在第 $0$ 天晚上显示的数字。

输出格式

对于每个测试用例，输出一行一个整数，表示满足 $i < j$ 且灯塔 $i$ 和 $j$ 是同步的数对 $(i, j)$ 的数量。

样例输入 1

4
5
7 4 16 4 2
4
1 7 10 100
3
4 16 37
3
2 20 4

样例输出 1

1
6
0
1

说明

样例解释

• 在第一个测试用例中：
  • 灯塔 $1$ 从 $7$ 开始：$7 \to 49 \to 97 \to 130 \to 10 \to 1$，然后永远停留在 $1$。
  • 灯塔 $2$ 和灯塔 $4$ 都从 $4$ 开始，所以它们每天晚上显示的数字都相同，是同步的。
  • 灯塔 $3$ 从 $16$ 开始，灯塔 $5$ 从 $2$ 开始；它们虽然都会进入一个循环，但处于循环的不同位置，永远无法在同一天晚上显示相同的数字。 所以唯一同步的数对是 $(2, 4)$，答案是 $1$。
• 在第二个测试用例中，所有的灯塔迟早都会变成 $1$ 并且永远停留在那里，因此它们两两之间都是同步的，共有 $6$ 对。
• 在第四个测试用例中，在第 $1$ 天晚上，灯塔 $2$ 显示 $2^2+0^2=4$，而灯塔 $1$ 显示 $2^2=4$。从第 $1$ 天晚上开始，它们将永远相同。灯塔 $3$ 在第 $0$ 天晚上就开始显示 $4$，它比另外两个灯塔超前了一个晚上的进度，因此它与谁都不同步。唯一同步的数对是 $(1, 2)$，答案是 $1$。

数据范围

• 对于所有测试点，保证 $1 \le t \le 1000$。
• 对于每个测试用例，保证 $1 \le n \le 1000$。
• 对于每个测试用例，保证 $1 \le a_i \le 10^9$。
• 保证同一测试点内所有测试用例的 $n$ 之和不超过 $1000$。
• 保证所有的输入数值均为整数。