Поллі Хоче Крекер#3116
У піратському суспільстві існує правило: кожен капітан повинен мати домашнього улюбленця. Ця тварина має завжди сидіти на плечі капітана, особливо коли той розмовляє з добрими героями, що кидають йому виклик за його злі справи.
Жаднюгобородь є одним із найвідоміших і найнебезпечніших капітанів піратського корабля на ім'я Великограбіжник. Його улюбленець також славиться своєю лихістю — папуга Поллі. Як і будь-який папуга, Поллі любить наслідувати почуті розмови. На жаль, Поллі не надто вправний у копіюванні почутих речень. Через це Жаднюгобородь взяв на себе завдання допомогти Поллі у навчанні людської мови.
Жаднюгобородь помітив, що Поллі може наслідувати цілі речення, але часто робить одну або кілька з наступних трьох помилок:
Поллі плутає порядок слів у реченні. Наприклад, замість "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