문자열

연구소 RIGS는 무한 문자열을 만드는 새로운 방법을 연구하고 있다.

빈 문자열 $S_{0}^{(k)} = \varepsilon$에서 시작한다. 다음 버전은 다음과 같이 만든다. 현재 버전을 $k$번 반복해 이어 붙인 뒤, 연속한 두 복사본 사이마다 임의의 기호를 하나씩 넣는다. 모든 버전에서 같은 $k$를 쓰지만, 넣는 기호는 버전마다 달라도 된다. 이 과정을 계속하면 무한 문자열 $S_{\infty}^{(k)}$가 된다.

예를 들어 $k = 3$일 때 $S_{1}^{(3)} = \mathtt{rt}$라고 하자. 이를 세 번 반복하고 $\mathtt{x}$와 $\mathtt{r}$을 넣으면 $S_{2}^{(3)} = \mathtt{rtxrtrrt}$가 된다. $S_{3}^{(3)}$은 $S_{2}^{(3)}$, $\mathtt{a}$, $S_{2}^{(3)}$, $\mathtt{r}$, $S_{2}^{(3)}$을 차례로 이어 붙인 것이다.

길이가 $n$인 문자열 $A$가 주어진다. $A$는 $S_{\infty}^{(k)}$의 접두사이다. $A$를 접두사로 가지는 $S_{\infty}^{(k)}$를 위의 방법으로 만들 수 있는 최소의 $k$를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이후 $T$개의 줄에 테스트가 하나씩 주어진다. 각 테스트는 비어 있지 않으며 소문자 라틴 알파벳으로만 이루어져 있다. 테스트 케이스의 개수는 $10^5$을 넘지 않고, 모든 테스트 문자열 길이의 합은 $10^6$을 넘지 않는다.

정확히 $T$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 테스트에 대한 최소 $k$를 출력한다.