가장 짧은 주기

문자열 $t$가 문자열 $s$의 주기라는 것은, $|t| \le |s|$이고 어떤 양의 정수 $k$에 대해 $s$가 $t^k$($t$를 $k$번 이어 붙인 문자열)의 접두사가 되는 경우를 말한다. 예를 들어 단어 entente의 주기는 ent, entent, entente이며 그 길이는 각각 $3$, $6$, $7$이다. $s$의 가장 짧은 주기란 이러한 주기 중 길이가 가장 짧은 것을 뜻한다.

선생님이 칠판에 아주 긴 단어 하나를 적었다. 수업에 집중하지 않던 Bytie는 대신, 칠판에 적힌 단어에서 글자를 정확히 하나 지워 만들 수 있는 모든 단어를 공책에 옮겨 적었다. 칠판 단어의 길이가 $n$이면 공책에는 길이가 $n-1$인 단어가 $n$개 적힌다. 이제 Bytie는 공책에 적힌 단어들 중에서 가장 짧은 주기가 가장 짧은 단어를 고르려고 한다. 칠판 단어가 주어질 때, 그렇게 고른 단어의 가장 짧은 주기의 길이를 구하여라.

첫째 줄에 테스트 케이스의 개수 $d$ ($1 \le d \le 10$)가 주어진다. 이어지는 $d$개의 줄에 각 테스트 케이스가 하나씩 주어진다. 각 줄에는 칠판 단어의 길이 $n_i$ ($2 \le n_i \le 200000$), 공백 하나, 그리고 소문자 알파벳으로 이루어진 길이 $n_i$의 단어가 순서대로 주어진다.

$d$개의 줄을 출력한다. $i$번째 줄에는 정수 하나를 출력하는데, 이는 $i$번째 칠판 단어에서 글자를 정확히 하나 지워 만들 수 있는 모든 단어에 대해 가장 짧은 주기의 길이를 최소화한 값이다.

단어 ababcaba를 생각하자. Bytie가 공책에 적는 단어들과 각 단어의 가장 짧은 주기 길이는 다음과 같다.

다섯 번째 위치의 글자 c를 지우면 abababa가 되고, 이 단어의 가장 짧은 주기는 길이가 $2$이다. 다른 어떤 글자를 지워도 이보다 더 짧은 가장 짧은 주기는 얻을 수 없다. 따라서 답은 $2$이다.