Вам дана строка \(s\) длиной \(n\), состоящая из строчных латинских символов. Найдите длину самой короткой строки \(k\), такой что несколько (возможно одна) копий \(k\) могут быть сконкатенированы вместе, чтобы образовать строку той же длины, что и \(s\), и при этом имеется не более одного отличающегося символа.
Формально, найдите длину самой короткой строки \(k\), такой что \(c = \underbrace{k + \cdots + k}_{x\rm\ \text{раз}}\) для некоторого положительного целого \(x\), строки \(s\) и \(c\) имеют одинаковую длину и \(c_i \neq s_i\) для не более чем одного \(i\) (т.е. существует \(0\) или \(1\) такая позиция).
Выходные данные
Для каждого теста выведите длину самой короткой строки \(k\), удовлетворяющей условиям в условии.
Примечание
В первом примере вы можете выбрать \(k = \texttt{a}\) и \(k+k+k+k = \texttt{aaaa}\), которая отличается от \(s\) только во второй позиции.
Во втором примере вы не можете выбрать \(k\) длиной один или два. Мы можем взять \(k = \texttt{abba}\), которая равна \(s\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
abaa
4
abba
13
slavicgslavic
8
hshahaha
20
stormflamestornflame
|
1
4
13
2
10
|