Когда Махмуд и Ехаб готовились к Международной олимпиаде по информатике, они встретились с задачей о наибольшей общей подпоследовательности. Они ее решили, а после этого Ехаб задал Махмуду другую задачу.

Дано две строки a и b, найдите длину их наибольшей не общей подпоследовательности, то есть такой строки, которая является подпоследовательностью одной строки и не является подпоследовательностью другой.

Подпоследовательность некоторой строки это последовательность букв, которая встречается в том же порядке в строке, не обязательно подряд. Например, строки «ac», «bc», «abc» и «a» являются подпоследовательностями строки «abc», а строки «abbc» и «acb» — нет. Пустая строка является подпоследовательностью любой строки, любая строка является подпоследовательностью ее самой.