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