Полли Хочет Крекер
В обществе пиратов существует правило, что каждый капитан обязан приручить питомца. Это животное всегда должно находиться на плече капитана-пирата, особенно во время беседы с положительными героями, которые оспаривают его злые дела.
Жадная Борода - один из бесчестных и опасных капитанов пиратского корабля с названием Великий Мародер. Его питомец - бесчестный и опасный попугай Полли. Как и любой попугай, Полли любит имитировать разговоры, которые он слышит. К сожалению, Полли не очень хорошо имитирует предложения, которые он слышит. Поэтому Жадная Борода взял на себя обязательство помочь Полли, пока он учится говорить на человеческом языке.
Жадная Борода заметил, что Полли способен воспроизводить целые предложения, но он часто совершает одну или более из трех следующих ошибок:
Поли премешивает предложение, ставя все слова в неверном порядке. То есть вместо того чтобы сказать "polly wants a cracker", Полли говорит "polly cracker a wants";
Полли забывает некоторые слова из предложения. То есть вместо предложения "polly wants a cracker" Полли говорит "polly a cracker";
И наконец, Полли смешивает, добавляет или удаляет согласные и и гласные^1 буквы в своих словах. То есть вместо фразы "polly wants a cracker" Полли произносит "polly wantsu a trackets".
Обратите внимание, что Полли никогда не имитирует одно и то же слово дважды в предложении. Капитан всегда знает начальное предложение, которое Полли будет пытаться подражать.
Капитана Жадная Борода не интересуют первые две ошибки. Однако, смешивание букв или добавление/удаление букв из слова доводило его кровь до кипения. Поэтому каждый раз, когда Полли делает ошибки в предложении, изменяя буквы, капитан забирает один сухарик из его обеда для каждой измененной буквы. Количество крекеров, которое капитан забирает у Полли за слово, равно минимальному количеству изменений, необходимых для преобразования сказанного слово в слово, которое Полли хотел сказать. Изменением называется вставка, удаление или замена одной буквы.
Не всегда понятно, каким образом слова в имитированном предложении соответствуют словам в оригинальном предложении. Жадная Борода считает, что симитированные слова соответствуют исходным словам таким образом, что общее количество ошибок сведено к минимуму.
Например, если Полли должен был сказать "polly wants a cracker", но сказал "polly crackets wantsu", то капитан забирает у попугая 3 крекера из ужина. 2 крекера отбираются за изменение слова "cracker" и 1 крекер за добавление буквы в слове "wants". Капитан не обращает внимание на то, что слово "a" пропущено, как и на то, что слова произнесены в другом порядке.
_______________
^1 - Читается: изменение, добавление или удаление букв.
Входные данные
Первая строка содержит количество тестов. Каждый тест имеет следующий формат:
строка (1 ≤ длина ≤ 1000) - предложение, которое пытается имитировать Полли;
строка (1 ≤ длина ≤ 1000) - предложение, которое сказал Полли.
Дополнительные примечания:
имитируемое предложение содержит от одного до восьми слов.
словом являлется последовательность из букв нижнего регистра. После каждого слова находится либо пробел, либо конец предложения.
предложение не содержит несколько пробелов рядом.
Выходные данные
Для каждого теста вывести в отдельной строке количество крекеров, которое Жадная Борода удержит с обеда Полли.