Algorytmy 2
Najdłuższy wspólny podciąg
Napisz program, który znajduje długość najdłuższego wspólnego podciągu dwóch danych ciągów $X$ i $Y$.
W tym zadaniu ciągi $X$ i $Y$ składają się z małych i wielkich liter alfabetu angielskiego.
Wejście
Dane wejściowe składają się z wielu zestawów danych. W pierwszym wierszu podana jest liczba naturalna $q$ będąca liczbą zestawów danych. W kolejnych $2 \cdot q$ wierszach podany jest każdy zestaw danych składający się z dwóch napisów $X$ i $Y$.
Wyjście
Dla każdego zestawu danych wypisz w linii długość najdłuższego wspólnego podciągu $X$ i $Y$.
Ograniczenia
- $1 \le q \le 150$
- $1 \le$ długość $X \le 1000$
- $1 \le$ długość $Y \le 1000$
Przykłady
Wejście 1
3
abcbdab
bdcaba
abc
abc
abc
bc
Wyjście 1
4
3
2