Problem B
DNA Similarity

Image by Andy Leppard.

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.

3
agaatacg
atagatcagg
accggat
accggat
gggaaaggg
aaaccc

6
7
3