给定一个字符串 $$$s$$$,长度为 $$$n$$$,由小写拉丁字符组成。找到最短字符串 $$$k$$$ 的长度,使得 $$$k$$$ 的多个(可能是一个)副本可以连接在一起,形成一个与 $$$s$$$ 长度相同且最多一个不同字符的字符串。
更正式地,找到最短字符串 $$$k$$$ 的长度,使得 $$$c = \underbrace{k + \cdots + k}_{x\rm\ \text{times}}$$$ 对于某个正整数 $$$x$$$,字符串 $$$s$$$ 和 $$$c$$$ 具有相同的长度,并且 $$$c_i \neq s_i$$$ 对于 at大多数$$$i$$$(即存在$$$0$$$或$$$1$$$这样的位置)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — 字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含字符串 $$$s$$$,由小写拉丁字符组成。
所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。
输出
对于每个测试用例,打印满足语句中约束的最短字符串 $$$k$$$ 的长度。
示例
输入 #1
5 4 abaa 4 abba 13 slavicgslavic 8 hshahaha 20 stormflamestornflame
输出 #1
1 4 13 2 10
注意
在第一个测试用例中,您可以选择 $$$k = \texttt{a}$$$ 和 $$$k+k+k+k = \texttt{aaaa}$$$,仅与第二个位置的 $$$s$$$ 不同。
在第二个测试用例中,您不能选择长度为 1 或 2 的 $$$k$$$。我们可以有$$$k = \texttt{abba}$$$,它等于$$$s$$$。