Поллі Хоче Крекер
У піратському суспільстві існує правило: кожен капітан повинен мати улюбленця. Ця тварина завжди має сидіти на плечі капітана, особливо під час розмови з позитивними героями, які оскаржують його злі вчинки.
Жадібна Борода - один з найнебезпечніших капітанів піратського корабля під назвою Великий Мародер. Його улюбленець - безчесний і небезпечний папуга Поллі. Як і будь-який папуга, Поллі любить імітувати розмови, які він чує. На жаль, Поллі не завжди добре відтворює почуті речення. Тому Жадібна Борода вирішив допомогти Поллі навчитися говорити людською мовою.
Жадібна Борода помітив, що Поллі може відтворювати цілі речення, але часто робить одну або більше з трьох наступних помилок:
Поллі перемішує слова в реченні, ставлячи їх у неправильному порядку. Наприклад, замість "polly wants a cracker" Поллі каже "polly cracker a wants";
Поллі забуває деякі слова з речення. Наприклад, замість "polly wants a cracker" Поллі каже "polly a cracker";
І нарешті, Поллі змішує, додає або видаляє приголосні та голосні літери у своїх словах. Наприклад, замість "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) - речення, яке сказав Поллі.
Додаткові примітки:
імітоване речення містить від одного до восьми слів.
словом є послідовність з літер нижнього регістру. Після кожного слова знаходиться або пробіл, або кінець речення.
речення не містить кілька пробілів поруч.
Вихідні дані
Для кожного тесту вивести в окремому рядку кількість крекерів, які Жадібна Борода утримає з обіду Поллі.