유전자 함수

'인간 유전자 서열(Human Gene Function)'은 인간의 유전 정보를 담고 있는 서열입니다. 이 정보는 DNA 분자에 표현되며, DNA를 구성하는 염기는 아데닌(A), 구아닌(G), 티민(T), 사이토신(C)의 네 가지뿐입니다. 따라서 인간 유전자 서열은 A, G, T, C 네 문자로만 이루어집니다.

두 유전자 서열이 주어질 때, 두 서열이 얼마나 비슷한지를 나타내는 유사도(similarity) 를 다음과 같이 정의합니다.

• 두 서열 각각의 원하는 위치에 공백 문자 \* 를 적당히 삽입하여 두 문자열의 길이를 똑같게 만듭니다.
• 이렇게 정렬한 뒤, 같은 위치에 놓인 두 문자에 대해 아래 표에서 정해진 매칭값을 찾아 모두 더합니다.
• 단, 공백과 공백을 같은 위치에 놓는 것은 허용되지 않습니다(표에 값이 없습니다).
• 공백을 삽입하는 방법은 여러 가지이며, 그 중 매칭값의 합이 최대가 되는 값을 두 서열의 유사도라고 합니다.

매칭값 표(행과 열의 문자를 매칭했을 때의 값, \* 는 공백이며 공백끼리의 매칭은 불가능):

예를 들어 두 서열이 각각 AGTGATG 와 GTTAG 라고 합시다.

공백을 아래처럼 넣으면 매칭값의 합은 9가 됩니다.

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

하지만 아래처럼 넣으면 매칭값의 합은 14가 되며, 이것이 가능한 모든 방법 중 가장 큰 값입니다. 따라서 두 서열의 유사도는 14입니다.

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

두 서열이 주어질 때 유사도를 구하는 프로그램을 작성하세요.

첫째 줄에 테스트 케이스의 개수 T 가 주어집니다.

이어서 각 테스트 케이스마다 두 줄이 주어집니다. 각 줄에는 유전자 서열의 길이와 인간 유전자 서열이 공백으로 구분되어 주어집니다.

모든 인간 유전자 서열의 길이는 100을 넘지 않습니다.

각 테스트 케이스마다 주어진 두 인간 유전자 서열의 유사도를 한 줄에 하나씩 출력합니다.