Description

陆历川经过千辛万苦终于来到了雁归谷，听说这里有一个隐世高人冷酒，陆历川希望冷酒可以收下自己做徒弟，冷酒说，我可以收你做徒弟，但是你必须把下面这道题解对才有资格做我的徒弟 冷酒给了陆历川一串数字，要求陆历川告诉他循环节为$1，2，3，4$的字串的最大长度是几？

Format

Input

第一行$T$(0 $\lt$ $T$ $\lt$ 200) 每一个样例第一行一个数字$n$代表字串的长度(0 $\lt$ $n$ $\lt$ 2000) 接下来一行输入n个数字$k$ (0$\leq$$k$$\leq$ 9)

Output

输出循环节长度从$1$到$n$的子串的最大长度

Samples

2
11
1 2 3 4 5 6 7 8 9 0 1 
12
2 0 0 2 2 0 0 2 2 0 0 2

Case #1: 11 0 0 0 0 0 0 0 0 0 0
Case #2: 12 8 12 0 0 0 0 0 0 0 0 0