说明

故事是这样的——算了不想编故事了，总之这是一道签到题。传说中有这样一个图，它由n个顶点组成，对于每一个顶点i，它有且仅有一条通向(i^2+1)%n的路径，每个顶点都有一个一位数的权值。现有如下定义：对于图上的某一条路径，其价值为从起点到终点依次相连组成的数字（如若点V1的权值为1，V2的权值为2，V3的权值为3，则路径V1-V2-V3的价值为123）。试求出该图所有长度为n-1（即由n个顶点组成）的路径中价值最大的路径。

输入格式

第一行输入一个T表示测试数据组数。
对于每组测试数据，输入包括两行：

• 第一行一个整数n(1 <= n <= 10000)
• 第二行n个整数ai(0 <= ai <= 9)（中间没有空格）

输出格式

对于每组数据，输出长度为n-1的路径中价值最大的路径的价值。

样例

4
3
556
5
54321
7
7654123
10
1057066497

666
54354
7652222
9664105664