E. 近乎最短重复子串

时间限制：每个测试用例 $2$ 秒 内存限制：每个测试用例 $256$ 兆字节

给定一个长度为 $n$、由小写拉丁字母构成的字符串 $s$。 请找出最短的字符串长度 $k$，满足：将该字符串复制若干次后首尾拼接，可以形成一个与 $s$ 长度相同的字符串，且新串与 $s$ 最多只有一个位置的字符不同。

形式化描述

求出最小的 $k$，使得存在正整数 $x$，满足：

字符串 $s$ 与 $c$ 长度相等，且满足 $c_i\neq s_i$ 的下标 $i$ 的数量不超过 $1$（即存在 $0$ 个或 $1$ 个这样的位置）。

输入格式

第一行包含一个整数 $t$（$1\le t\le 10^3$），表示测试用例的数量。

对于每个测试用例：

1. 第一行包含一个整数 $n$（$1\le n\le 2\cdot 10^5$），表示字符串 $s$ 的长度。
2. 第二行包含一个由小写拉丁字母组成的字符串 $s$。

保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每个测试用例，输出一行一个整数，表示满足条件的最短字符串长度 $k$。

示例

输入

5
4
abaa
4
abba
13
slavicgslavic
8
hshahaha
20
stormflamestornflame

输出

1
4
13
2
10

注释

在第一个测试用例中，可以选取 $k=\texttt{a}$， 将其重复 $4$ 次得到 $c=\texttt{aaaa}$，该串与 $s$ 仅在第 $2$ 个位置字符不同。

在第二个测试用例中，无法选取长度为 $1$ 至 $2$ 的 $k$。 可以选取 $k=\texttt{abba}$，此时 $c$ 与 $s$ 完全相同。