题目描述

给定一个长度为 $n$、只由小写字母组成的字符串 $s$。求最短的字符串 $k$ 的长度，使得若干个（可以是一个）$k$ 首尾拼接起来，能得到一个与 $s$ 长度相同、且至多有一个位置不同的字符串。

更形式化地说：求最短的字符串 $k$ 的长度，使得存在正整数 $x$，令 $c = \underbrace{k + \cdots + k}_{x\ \text{个}}$，满足 $s$ 与 $c$ 长度相同，并且 $c$ 与 $s$ 不同的位置不超过 $1$ 个。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^3$），表示数据组数。

每组数据的第一行包含一个整数 $n$（$1 \leq n \leq 2\cdot10^5$），表示字符串长度。

第二行包含字符串 $s$，由小写字母组成。

所有测试数据的 $n$ 之和不超过 $2\cdot10^5$。

输出格式

对每组数据，输出满足条件的最短字符串 $k$ 的长度。

说明

第一组样例中，取 $k = \texttt{a}$，则 $k+k+k+k = \texttt{aaaa}$，它只在第 $2$ 个位置与 $s$ 不同。

第二组样例中，长度为 $1$ 或 $2$ 的 $k$ 都不行；取 $k = \texttt{abba}$ 时，拼出的串与 $s$ 完全相同。

样例

5
4
abaa
4
abba
13
slavicgslavic
8
hshahaha
20
stormflamestornflame

1
4
13
2
10

来源

Codeforces Round 937 (Div. 4) E 题