Given two DNA sequences (strings of symbols a, c, g, t), calculate their similarity. For this problem we define similarity as the length of the longest subsequence that is common to both original sequences. A subsequence is a sequence of symbols that appears in a longer sequence in the same order, but with some symbols from the longer sequence possibly removed. For example, consider the following two sequences:
The longest subsequence of both sequences is agatcg, with a length of $6$. Here are the original sequences again, but this time using uppercase letters to indicate the longest subsequence:
Note that there may be more than one subsequence with the longest length.
Input begins with an integer $n$ indicating the number of cases that follow, where $1 \le n \le 100$. Each test case has two lines which represent the two sequences to compare. Each sequence is non-empty and has up to $500$ characters, consisting only of the letters a, c, g, and t.
For each pair of sequences, output the length of the longest common subsequence.
|Sample Input 1||Sample Output 1|
3 agaatacg atagatcagg accggat accggat gggaaaggg aaaccc
6 7 3