Поликарп увлекается изучением берляндских иероглифов. Как-то раз Поликарп раздобыл два древних берляндских рисунка, на каждом из которых была нарисована окружность из иероглифов. Известно, что ни один иероглиф не встречается дважды ни в первой окружности, ни во второй (но может встречаться по одному разу в каждой из них).

Поликарп хочет записать эти изображения к себе в ноутбук, но — увы — ноутбуки не позволяют записывать иероглифы окружностями. Поэтому Поликарп вынужден разорвать каждую окружность и записать все ее иероглифы в порядке обхода по часовой стрелке в одну строку. Строку, полученную из первой окружности, будем называть a, а полученную из второй — b.

Вариантов разорвать окружности из иероглифов достаточно много, поэтому Поликарп выбирает такой способ, что длина наибольшей подстроки строки a, которая встречается как подпоследовательность в строке b, максимальна.

Помогите Поликарпу — найдите максимальную возможную длину искомой подстроки (подпоследовательности) при оптимальном разрыве первой и второй окружностей.

Длиной строки s называется количество символов в ней. Если длина строки s обозначается |s|, строку можно записать s в виде s = s₁s₂... s_|s|.

Непустую строку x = s[a... b] = s_as_a + 1... s_b (1 ≤ a ≤ b ≤ |s|) будем называть подстрокой строки s. Например, «code» и «force» — подстроки «codeforces», а «coders» — нет.

Непустую строку y = s[p₁p₂... p_|y|] = s_p1s_p2... s_p|y| (1 ≤ p₁ < p₂ < ... < p_|y| ≤ |s|) будем называть подпоследовательностью строки s. Например, «coders» — подпоследовательность «codeforces».