#CW41. 灯塔同步(number)

灯塔同步(number)

题目描述

小 W 观察着一排灯塔。第 00 天第 ii 座灯塔显示正整数 aia_i。从下一天开始,每座灯塔都独立地执行同一条规则:若当天显示 xx,则下一天显示 xx 的十进制表示中各位数字的平方和。

例如,23→22+32=13→12+32=10→123 \to 2^2+3^2=13 \to 1^2+3^2=10 \to 1,之后始终显示 11。

如果存在某一天,从这一天起两座灯塔在每一天显示的数都完全相同,则称这两座灯塔是同步的。请计算同步的灯塔对数 (i,j)(i,j)(i<ji<j)。

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例包含两行:第一行一个整数 nn;第二行 nn 个正整数 a1,…,ana_1,\dots,a_n。

输出格式

对于每个测试用例,输出一个整数,表示同步灯塔对数。

样例 1 输入

1
5
7 4 16 4 2

样例 1 输出

1

样例 1 解释

数字 44 的变化序列为 4,16,37,58,89,…4,16,37,58,89,\dots,两个编号为 44 的灯塔从第一天起始终同步。其余灯塔与它们的变化阶段不同,因此答案为 11。

数据范围

所有测试点满足 1≤T≤10001 \le T \le 1000,1≤n≤10001 \le n \le 1000,所有测试用例的 nn 之和不超过 10001000,且 1≤ai≤1091 \le a_i \le 10^9。

本题采用捆绑计分;只有一个子任务及其依赖的所有子任务全部通过时,才能获得该子任务分数。

子任务 分值 测试点 额外限制 依赖
1 20 1∼41\sim 4 n≤5n \le 5 且 ai≤100a_i \le 100 无
2 5∼85\sim 8 n≤20n \le 20 且 ai≤104a_i \le 10^4
3 9∼129\sim 12 n≤100n \le 100 且 ai≤106a_i \le 10^6 1, 2
4 13∼1613\sim 16 n≤500n \le 500 1, 2, 3
5 17∼2017\sim 20 无额外限制 1, 2, 3, 4