Przyjęcie

To zadanie pochodzi z Spoja. Tam też znajdują się testy do zadania.
Jeśli Twoje rozwiązanie zostanie pozytywnie ocenione na tamtych testach, należy wysłać tu zgłoszenie wypisujące "Zrobione".

Limit pamięci: 256MB

Dane są dwa słowa, A i B. Odpowiedz, ile conajmniej trzeba wykonać operacji, by zmienić A w B? Dozwolone operacje to:

  • Usuń jedną literę z jednego ze słów
  • Dodaj jedną literę do jednego ze słów
  • Zamień jedną literę z jednego ze słów na pewną inną

Wejście

W pierwszym wierszu wejścia podana jest liczba T <= 10 - liczba przypadków testowych. Dla każdego przypadku testowego podane są w dwóch liniach dwa słowa A i B. Oba słowa będą się składać tylko z wielkich liter angielskiego alfabetu, a ich długości nie przekroczą 2000 znaków.

Wyjście

Dla każdego testu w osobnej linii wypisz minimalną potrzebną liczbę operacji.

Przykład

Wejście:
1
FOOD
MONEY

Wyjście:
4

PS: Spoj jest całkiem fajną platformą zawierającą krótkie zadanka na zaklepanie konkretnej rzeczy. Polecam, jeśli szukacie zadania żeby klepnąć czysty przepływ/skojarzenie/inny ciekawy algorytm i nie chcecie się bawić w wykminienie i przebudowę algorytmu na rzecz zadania.