题目描述

给你一个长度为 $n$ 的字符串 $s$ ，它由小写字母组成。求最短字符串 $k$ 的长度，使得多个（可能是一个） $k$ 可以连接在一起，形成一个长度与 $s$ 相同的字符串，且最多只有一个不同的字符。

更正式地说，求最短字符串 $k$ 的长度，使得 $c = \underbrace{k + \cdots + k}_{x\rm\ \text{times}}$ 为某个正整数 $x$ ，字符串 $s$ 和 $c$ 的长度相同，且 $c_i \neq s_i$ 中最多有一个 $i$ （即存在 $0$ 或 $1$ 这样的位置）。

输入格式

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$ .

样例 #1

样例输入 #1

5
4
abaa
4
abba
13
slavicgslavic
8
hshahaha
20
stormflamestornflame

样例输出 #1

1
4
13
2
10