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