Яблоки и бананы вкусные, но и опасные. Одно древнее пророчество гласит, что если Вы расположите их в некотором порядке, то мир ждет катастрофа! Однажды, хмурым облачным днем, когда Вам этот мир уже совсем надоел, Вы решили испытать этот факт. Перед Вами расположены в ряд несколько бананов и апельсинов. Над ними разрешено выполнять только одну операцию: на каждом шаге можно выбрать произвольное количество последовательно лежащих фруктов и заменить его на такое же количество фруктов одного типа. Вам не надо уничтожать мир, Вам надо знать наименьшее количество операций, за которое можно это сделать.
Первая строка содержит количество тестов t
(t ≤ 100
). Каждый тест состоит из двух строк, первая из которых содержит начальное расположение фруктов, а вторая – расположение, ведущее к катастрофе. Обе строки содержат только две буквы: 'A
' – яблоко, 'B
' – банан. Обе строки имеют равную длину, не большую 200. Строки не содержат пробелов ни в начале, ни в конце.
Для каждого теста вывести в отдельной строке количество операций, ведущих к уничтожению мира.