У вашего одноклассника, которого вы не очень любите за его занудство, но уважаете за его ум, были обнаружены две строки: строка \(s\) длины \(n\) и строка \(t\) длины \(m\).
Последовательность индексов \(p_1, p_2, \ldots, p_m\), где \(1 \leq p_1 < p_2 < \ldots < p_m \leq n\), называется хорошей, если \(s_{p_i} = t_i\) для всех \(i\) от \(1\) до \(m\). Шириной последовательности называется величина \(\max\limits_{1 \le i < m} \left(p_{i + 1} - p_i\right)\).
Помогите однокласснику найти хорошую последовательность индексов с максимальной шириной. Одноклассник обещал вам, что строки \(s\) и \(t\) таковы, что хотя бы одна хорошая последовательность точно существует.
Выходные данные
Выведите одно число — максимальную ширину хорошей последовательности.
Примечание
В первом примере существует две хороших последовательности с шириной \(3\): это \(\{1, 2, 5\}\) и \(\{1, 4, 5\}\).
Во втором примере хорошая последовательность максимальной ширины — это \(\{1, 5\}\).
В третьем примере есть лишь одна хорошая последовательность — это \(\{1, 2, 3, 4, 5\}\).
В четвёртом примере есть лишь одна хорошая последовательность — это \(\{1, 2\}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
abbbc
abc
|
3
|
|
2
|
5 2
aaaaa
aa
|
4
|
|
3
|
5 5
abcdf
abcdf
|
1
|
|
4
|
2 2
ab
ab
|
1
|