蚂蚁 Welly 现在致力于城市基础设施建设。他来到了数字王国，请求觐见国王。他讲述了自己如何在幸福王国建造了一条幸福之路。国王认可了 Welly 的才华，并希望这份才华能帮助他在周年纪念日之前找到最佳的无限分数路径。

该王国共有 $N$ 座城市，编号从 $0$ 到 $N-1$。给定一个包含十进制数字的数组 $D[0 \dots N-1]$（$0 \le D[i] \le 9$，$D[i]$ 为整数）。从第 $i$ 座城市出发的唯一单向道路通往编号为 $(i^2 + 1) \% 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$ 位数字。

样例

输入 1

4
3
149
5
12345
7
3214567
9
261025520

输出 1

Case #1: 999
Case #2: 53123
Case #3: 7166666
Case #4: 615015015