该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

这对无从翱翔的背羽上

背负无数罪孽 却又消失不见

请在你心中安放一份 相对而言 始抽新绿的人性

将我寻出

能否在那孕育了未来的艳阳之下 执爱之手一同逃离？

下次相遇 定是在你我皆未知的

这方天地之外

Your side is reserved forever(你的位置永远为你保留)

Don't be afraid of the vast road ahead(不必畏惧前方漫漫长路)

May I recall your face at the edge of this timeline(能否在时间尽头忆起你容颜)

We go from this garden enclosed by utopia(我们一同走出这座乌托邦围筑的花园)

题目描述

黯 与 萤 迫降在黑天鹅港。

那里有 $n$ 座灯塔，矗立在悬崖尽头，面向漆黑的大海。它们不发光。每一夜，火焰都会在石壁上烧出一个数字，像是某种古老的咒文，又像是谁在黑暗中反复念诵的名字。

黑天鹅港的灯塔背负着一条无法违抗的法则：如果一座灯塔今晚显示 $x$，那么明晚它显示的就是 $x$ 的十进制各位数字的平方和。

例如，一座显示 $23$ 的灯塔明天会显示 $2^2+3^2=13$，然后是 $1^2+3^2=10$，再然后是 $1$。

没有人知道这条法则从何而来，也没有人知道它要持续到哪一夜。它只是每晚准时降临，把所有数字推向各自的结局。

在季节的第 $0$ 晚，灯塔 $i$ 显示的数字是 $a_i$。从那一晚开始，诅咒每晚生效一次，直到永远。

有些数字最终停在 $1$，从此不再改变，像是终于被允许安息。 有些数字则坠入同一个循环，在黑暗里反复旋转，永远回不到起点，也永远走不出去。那不是解脱，而是另一种形式的永恒囚禁。

黯 与 萤 站在灯塔之间，看着那些数字一夜一夜地变化。

萤 说，如果两座灯塔在某个夜晚之后，每晚都显示完全相同的数字，直到永远，那它们就是合拍的。

就像两个背负着同样诅咒的人，在无数个错开的夜晚之后，终于走进了同一条轨迹。 从此以后，无论世界如何变化，它们都再也不会分开。

黯 问：有多少对 $(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$ 合拍的对数。

输入输出样例 #1

输入 #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$ 从 $4$ 开始，所以它比它们都早一晚。它曾经离它们那么近，却终究错开，与它们都不合拍。