2015
07-16

# Base pairing

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.

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.

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.

3
ATC
GAT
ATCG
TGC
CTAG
TGAT

1
2
3
Hint



1. 真的有点不懂了，你是什么派？“再说了，当今世界，哪个国家被帝国主义肢解了?仅仅换一个政权罢了。即使新换的政权，也不一定都是美国人说了算，伊拉克、利比亚、俄罗斯，谁听美国的?”