311212: CF1950E. Nearly Shortest Repeating Substring

E. Nearly Shortest Repeating Substringtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a string $s$ of length $n$ consisting of lowercase Latin characters. Find the length of the shortest string $k$ such that several (possibly one) copies of $k$ can be concatenated together to form a string with the same length as $s$ and, at most, one different character.

More formally, find the length of the shortest string $k$ such that $c = \underbrace{k + \cdots + k}_{x\rm\ \text{times}}$ for some positive integer $x$, strings $s$ and $c$ has the same length and $c_i \neq s_i$ for at most one $i$ (i.e. there exist $0$ or $1$ such positions).

Input

The first line contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2\cdot10^5$) — the length of string $s$.

The second line of each test case contains the string $s$, consisting of lowercase Latin characters.

The sum of $n$ over all test cases does not exceed $2\cdot10^5$.

Output

For each test case, print the length of the shortest string $k$ satisfying the constraints in the statement.

ExampleInput

5
4
abaa
4
abba
13
slavicgslavic
8
hshahaha
20
stormflamestornflame

Output

1
4
13
2
10

Note

In the first test case, you can select $k = \texttt{a}$ and $k+k+k+k = \texttt{aaaa}$, which only differs from $s$ in the second position.

In the second test case, you cannot select $k$ of length one or two. We can have $k = \texttt{abba}$, which is equal to $s$.

题目大意：
给定一个由小写拉丁字母组成的字符串 s，长度为 n。要找到一个最短的字符串 k，使得 k 的多个（可能是一个）副本连接起来形成一个与 s 长度相同的字符串，并且最多只有一个字符不同。

更正式地说，找到一个最短的字符串 k，使得 c = k + ... + k（x 次）对于某个正整数 x，字符串 s 和 c 有相同的长度，并且最多只有一个位置 i 使得 c_i ≠ s_i（即存在 0 个或 1 个这样的位置）。

输入数据格式：
第一行包含一个整数 t（1 ≤ t ≤ 10^3）——测试用例的数量。
每个测试用例的第一行包含一个整数 n（1 ≤ n ≤ 2·10^5）——字符串 s 的长度。
每个测试用例的第二行包含一个由小写拉丁字母组成的字符串 s。
所有测试用例的 n 之和不超过 2·10^5。

输出数据格式：
对于每个测试用例，输出满足题目条件的最短字符串 k 的长度。

示例：
输入
```
5
4
abaa
4
abba
13
slavicgslavic
8
hshahaha
20
stormflamestornflame
```
输出
```
1
4
13
2
10
```

注意：
在第一个测试用例中，可以选择 k = 'a'，那么 k+k+k+k = 'aaaa'，这与 s 只在第二个位置上不同。
在第二个测试用例中，不能选择长度为一或二的 k。可以选择 k = 'abba'，这与 s 相同。题目大意： 给定一个由小写拉丁字母组成的字符串 s，长度为 n。要找到一个最短的字符串 k，使得 k 的多个（可能是一个）副本连接起来形成一个与 s 长度相同的字符串，并且最多只有一个字符不同。 更正式地说，找到一个最短的字符串 k，使得 c = k + ... + k（x 次）对于某个正整数 x，字符串 s 和 c 有相同的长度，并且最多只有一个位置 i 使得 c_i ≠ s_i（即存在 0 个或 1 个这样的位置）。 输入数据格式： 第一行包含一个整数 t（1 ≤ t ≤ 10^3）——测试用例的数量。 每个测试用例的第一行包含一个整数 n（1 ≤ n ≤ 2·10^5）——字符串 s 的长度。 每个测试用例的第二行包含一个由小写拉丁字母组成的字符串 s。 所有测试用例的 n 之和不超过 2·10^5。 输出数据格式： 对于每个测试用例，输出满足题目条件的最短字符串 k 的长度。 示例： 输入 ``` 5 4 abaa 4 abba 13 slavicgslavic 8 hshahaha 20 stormflamestornflame ``` 输出 ``` 1 4 13 2 10 ``` 注意： 在第一个测试用例中，可以选择 k = 'a'，那么 k+k+k+k = 'aaaa'，这与 s 只在第二个位置上不同。 在第二个测试用例中，不能选择长度为一或二的 k。可以选择 k = 'abba'，这与 s 相同。