Поликарп исследует строку, которую он называет абракадабра. Эта строка строится по следующему алгоритму:

• На первом шаге строка состоит из одного символа «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-ом шаге, будет состоять из 2^k - 1 символов.

Поликарп записал строку, полученную после 30 шагов данного алгоритма, и выбрал из нее две непустые подстроки. Ваша задача состоит в том, чтобы найти длину наибольшей общей подстроки двух подстрок, выбранных Поликарпом.

Подстрокой s[i... j] (1 ≤ i ≤ j ≤ |s|) строки s = s₁s₂... s_|s| называется строка, равная s_is_i + 1... s_j. Например, подстрока s[2...4] строки s = «abacaba» равна «bac». Сама строка является своей подстрокой.

Наибольшей общей подстрокой двух строк s и t называется самая длинная строка, которая является подстрокой как s, так и t. Например, наибольшей общей подстрокой «contest» и «systemtesting» является строка «test». Общих подстрок наибольшей длины может существовать несколько.