8623: ALDS1_10_C : Longest Common Subsequence
Description
For given two sequences X and Y, a sequence Z is a common subsequence of X and Y if Z is a subsequence of both X and Y.
For example, if X={a,b,c,b,d,a,b} and Y={b,d,c,a,b,a}, the sequence {b,c,a} is a common subsequence of both X and Y. On the other hand, the sequence {b,c,a} is not a longest common subsequence (LCS) of X and Y, since it has length 3 and the sequence {b,c,b,a}, which is also common to both X and Y, has length 4. The sequence {b,c,b,a} is an LCS of X and Y, since there is no common subsequence of length 5 or greater.
Write a program which finds the length of LCS of given two sequences X and Y. The sequence consists of alphabetical characters.
Input
The input consists of multiple datasets. In the first line, an integer q which is the number of datasets is given.
In the following 2×q lines, each dataset which consists of the two sequences X and Y are given.
Output
Constraints
1≤ length of X and Y ≤1,000
q≤20 if the dataset includes a sequence whose length is more than 100
Sample 1 Input
3
abcbdab
bdcaba
abc
abc
abc
bc
Sample 1 Output
4
3
2