P17071 [ICPC 2017 Shenyang R] Infinite Fraction Path

蚂蚁 Welly 现在致力于城市基础设施建设。他来到了数字王国，并请求觐见国王。他向国王讲述了他在欢乐王国修建一条欢乐之路的经历。国王肯定了 Welly 的才能，并希望这份才能可以帮助他在周年庆典之前找到最优的无限小数路径。 数字王国拥有 $N$ 座城市，编号从 $0$ 到 $N - 1$，同时你会得到一个由十进制数码组成的数组 $D[0 \cdots N - 1]$（$0 \le D[i] \le 9$，$D[i]$ 为整数）。从第 $i$ 座城市出发的唯一条单向道路，其目的地是编号为 $(i^2 + 1) \bmod N$ 的城市。 一条从第 $i$ 座城市出发的路径会依次经过城市 $u_1, u_2, u_3 \dots$。这条路径将构造一个实数 $A[i]$，称为相关小数，其整数部分恒为零，小数部分是一个无限十进制小数，各位数码依次为 $D[i], D[u_1], D[u_2], \dots$。 最优无限小数路径是指相关小数最大的那一条。

本题包含多组测试数据。第一行提供一个不超过 $100$ 的整数，表示测试数据的总组数。 对于每组测试数据，第一行包含整数 $N$（$1 \le N \le 150000$）。第二行包含数码数组 $D$，以无空格的连续字符串形式给出。 所有测试数据的 $N$ 之和小于 $2000000$。

对于每组测试数据，你应首先输出该组数据的编号标头。随后，你需要输出恰好 $N$ 个字符，表示最大的相关小数的小数部分的前 $N$ 位。

翻译由 DeepSeek V3.2 完成