Problem Description
We have two straight parallel DNA single strands. You can shift any strand left or right, but you can not reverse it or bent it.
Your task is to calculate how many paired bases at most between the two strands. Note that the paired bases can only be A-T, T-A, C-G or G-C.
Input
There is an integer T (1 <= T <= 100) in the first line, indicates there are T test cases in total.
For each test case, there are two lines, and each line contains one DNA single strand. You can assume that there are only “A”, “T”, “C” or “G” in the two strands. The length of each strand is at least 1 and not more than 30000.
There are at most 10 test cases that satisfy the total length of the two strands is more than 200.
Output
For each test case, you should output the correct answer in one line.
Sample Input
3
ATC
GAT
ATCG
TGC
CTAG
TGAT
Sample Output
1
2
3
