Браслеты
Наконец-то, Мегамозг разработал идеальный план, чтобы победить своего заклятого врага, Метро-Мэна! Он создал пару круглых энергетических браслетов, которые нужно носить на левой и правой руках. На каждом браслете выгравирована последовательность магических глифов (т.е. символов); каждый активированный глиф увеличивает силу Мегамозга на мощь одного гризли!
Однако есть одна загвоздка: браслеты работают только тогда, когда активированные подпоследовательности глифов на каждом браслете идентичны. Например, если у нас есть пара браслетов, глифы которых представлены строками "metrocity" и "kryptonite", то оптимальная активация глифов даст Мегамозгу силу 10 гризли:
Рисунок 1: Энергетические браслеты Мегамозга
На первом браслете активируются буквы "etoty" по часовой стрелке; те же буквы активируются против часовой стрелки на втором браслете. В общем случае порядок букв важен, но ориентация активированной подпоследовательности на каждом браслете (т.е. по часовой или против часовой стрелке) может быть одинаковой или разной — и не забывайте, что браслеты круговые!
Помогите Мегамозгу победить Метро-Мэна, определив оптимальные подпоследовательности глифов, необходимые для активации его браслетов.
Входные данные
Входной файл будет содержать не более 100 тестов (включая не более 5 "больших" тестов). Каждый тест представлен одной строкой, содержащей пару строк s и t, разделённых пробелом, соответствующих последовательностям глифов на левых и правых энергетических браслетах Мегамозга, соответственно. Каждая строка будет состоять только из строчных букв ('a'-'z'). Длина каждой входной строки будет от 1 до 100 символов включительно, за исключением больших тестов, где длина каждой входной строки будет от 1 до 1500 символов включительно.
Выходные данные
Для каждого теста выведите максимальную силу (в единицах гризли), которую Мегамозг сможет достичь, активировав глифы на своих браслетах.