# Problem B

DNA Similarity

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:

agaatacg atagatcagg

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:

AGaATaCG AtaGATCagG

Note that there may be more than one subsequence with the longest length.

## Input

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`.

## Output

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 |