Gene Function

A human gene function sequence carries human genetic information. This information is expressed in the DNA molecule, and because DNA is built from only four bases -- adenine (A), guanine (G), thymine (T), and cytosine (C) -- a human gene sequence consists solely of the four letters A, G, T, and C.

Given two gene sequences, we want to measure how alike they are with a value called the similarity, defined as follows.

• Insert blank characters \* at chosen positions in each sequence so that the two strings become the same length.
• After this alignment, for every position take the matching value of the two aligned characters from the table below and add them all up.
• A blank may never be aligned with another blank (the table has no value for that pair).
• Blanks can be inserted in many ways; the maximum possible sum of matching values over all ways is the similarity of the two sequences.

Matching-value table (value for pairing the row character with the column character; \* is a blank, and blank-with-blank is not allowed):

For example, suppose the two sequences are AGTGATG and GTTAG.

If the blanks are inserted as below, the sum of matching values is 9.

AGTGAT*G
*GT**TAG
→ (-3)+5+5+(-2)+(-3)+5+(-3)+5 = 9

But if the blanks are inserted as below, the sum becomes 14, which is the largest value over all possible ways. Hence the similarity of the two sequences is 14.

AGTGATG
*GTTA*G
→ (-3)+5+5+(-2)+5+(-1)+5 = 14

Write a program that, given two sequences, computes their similarity.

The first line contains the number of test cases T.

Each test case then consists of two lines. Each line contains the length of a gene sequence and the human gene sequence itself, separated by a space.

The length of every human gene sequence does not exceed 100.

For each test case, print the similarity of the two given human gene sequences, one per line.