На день рождения Коле подарили строку s, состоящую из маленьких латинских букв. Он, недолго думая, дописал к ней еще k символов справа.
После этого пришел Боря и сказал, что в новой строке, в качестве подстроки, есть тандемный повтор длины l. Насколько большим могло быть l?
Определение тамдемного повтора дано в примечании.
Выходные данные
Выведите одно число — максимальную длину тандемного повтора, который мог встретится в новой строке.
Примечание
Тандемным повтором длины 2n называется строка s, в которой для любой позиции i (1 ≤ i ≤ n) выполняется si = si + n.
В первом примере Коля мог получить строку aabaab, во втором — aaabbbbbb, в третьем — abracadabrabracadabra.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
aaba
2
|
6
|
|
2
|
aaabbbb
2
|
6
|
|
3
|
abracadabra
10
|
20
|