题目描述
小 W 观察着一排灯塔。第 0 天第 i 座灯塔显示正整数 ai。从下一天开始,每座灯塔都独立地执行同一条规则:若当天显示 x,则下一天显示 x 的十进制表示中各位数字的平方和。
例如,23→22+32=13→12+32=10→1,之后始终显示 1。
如果存在某一天,从这一天起两座灯塔在每一天显示的数都完全相同,则称这两座灯塔是同步的。请计算同步的灯塔对数 (i,j)(i<j)。
输入格式
第一行一个整数 T,表示测试用例数。
每个测试用例包含两行:第一行一个整数 n;第二行 n 个正整数 a1,…,an。
输出格式
对于每个测试用例,输出一个整数,表示同步灯塔对数。
样例 1 输入
1
5
7 4 16 4 2
样例 1 输出
1
样例 1 解释
数字 4 的变化序列为 4,16,37,58,89,…,两个编号为 4 的灯塔从第一天起始终同步。其余灯塔与它们的变化阶段不同,因此答案为 1。
数据范围
所有测试点满足 1≤T≤1000,1≤n≤1000,所有测试用例的 n 之和不超过 1000,且 1≤ai≤109。
本题采用捆绑计分;只有一个子任务及其依赖的所有子任务全部通过时,才能获得该子任务分数。
| 子任务 |
分值 |
测试点 |
额外限制 |
依赖 |
| 1 |
20 |
1∼4 |
n≤5 且 ai≤100 |
无 |
| 2 |
5∼8 |
n≤20 且 ai≤104 |
| 3 |
9∼12 |
n≤100 且 ai≤106 |
1, 2 |
| 4 |
13∼16 |
n≤500 |
1, 2, 3 |
| 5 |
17∼20 |
无额外限制 |
1, 2, 3, 4 |