Поликарп исследует строку, которую он называет абракадабра. Эта строка строится по следующему алгоритму:
- На первом шаге строка состоит из одного символа «a».
- На k-oм шаге Поликарп соединяет две копии строки, полученной на k - 1 шаге, а между ними вставляет k-й символ алфавита. Поликарп использует алфавит, состоящий из строчных латинских букв и цифр (всего 36 символов). Символы алфавита нумеруются следующим образом: 1-й символ — «a», 2-й — «b», ..., 26-й — «z», 27-й — «0», 28-й — «1», ..., 36-й — «9».
Рассмотрим алгоритм подробнее. На втором шаге Поликарп соединит две строки «a», вставив посередине символ «b», и получит строку «aba». На третьем шаге получится строка «abacaba», а на четвертом — «abacabadabacaba». Таким образом, строка, полученная на k-ом шаге, будет состоять из 2k - 1 символов.
Поликарп записал строку, полученную после 30 шагов данного алгоритма, и выбрал из нее две непустые подстроки. Ваша задача состоит в том, чтобы найти длину наибольшей общей подстроки двух подстрок, выбранных Поликарпом.
Подстрокой s[i... j] (1 ≤ i ≤ j ≤ |s|) строки s = s1s2... s|s| называется строка, равная sisi + 1... sj. Например, подстрока s[2...4] строки s = «abacaba» равна «bac». Сама строка является своей подстрокой.
Наибольшей общей подстрокой двух строк s и t называется самая длинная строка, которая является подстрокой как s, так и t. Например, наибольшей общей подстрокой «contest» и «systemtesting» является строка «test». Общих подстрок наибольшей длины может существовать несколько.
Примечание
В первом тесте первая подстрока равна «acab», вторая — «abac». У этих двух подстрок есть две наибольшие общие подстроки «ac» и «ab», нас же интересует только их длина — 2.
Во втором тесте первая подстрока равна «a», вторая — «c». У этих двух подстрок нет ни одного общего символа, поэтому длина наибольшей общей подстроки — 0.