题目描述

一个单词 $t$ 被称为 $s$ 的一个循环节当且仅当它的长度不超过 $t$ 并且存在一个整数 $k$ 使得 $s$ 是 $t^k$ 的一个前缀。比如 $\text{entente}$ 的循环节是 $\text{ent}$，$\text{entent}$ 和 $\text{entente}$。

Fotile 在黑板上写下了一个很长的单词。Seter 对 Fotile 的课不感兴趣，但是他把所有恰好在这个单词里删去一个字母的单词都写了下来。现在他想知道这些单词中拥有最短循环节的一个。

输入格式

第一行为数据组数 $T$。

每个数据包含一个数 $n$ 及一个长为 $n$ 的小写字母单词。

输出格式

输出最短循环节长度。

1
8 ababcaba

2

数据规模与约定

对于 $100\%$ 的数据，$1\le T\le 10$，$1\le n\le 2\times 10^5$。