如果一个单词 $t$ 的长度不超过单词 $s$，且存在自然数 $k$ 使得 $s$ 是 $t^k$ 的前缀，则称 $t$ 为 $s$ 的一个周期。例如，单词 entente 的周期有：ent、entent 和 entente。

老师在白板上写下了一个很长的单词。Bytie 对课堂内容不太感兴趣，但他把通过从白板上的单词中恰好删去一个字母所能得到的所有单词都记在了笔记本上。现在，他想从这些单词中选出一个，使其最短周期的长度最小。请编写一个程序来帮助他解决这个问题。

输入格式

标准输入的第一行包含一个整数 $d$ ($1 \le d \le 10$)，表示测试用例的数量。接下来有 $d$ 行，每行包含一个整数 $n_i$ ($2 \le n_i \le 200\,000$)，表示白板上单词的长度，以及一个由小写英文字母组成的长度为 $n_i$ 的单词。

输出格式

你的程序应向标准输出写入 $d$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案：一个整数，等于 Bytie 笔记本中所有单词的最短周期长度中的最小值。

样例

输入 1

1
8 ababcaba

输出 1

2

说明

样例解释：以下是 Bytie 记下的单词及其最短周期的长度：

• babcaba - 5,

• aabcaba - 6,

• abbcaba - 6,

• abacaba - 4,

• abababa - 2,

• ababcba - 6,

• ababcaa - 6,

• ababcab - 5.

我们可以看到，删去第五个位置的字母 c 后得到的单词，其最短周期长度为 2，且删去其他任何字母都无法得到更短的最短周期。