시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 24 18 17 73.913%

문제

'인간 유전자 서열(Human Gene Function)'이란 인간의 유전 정보를 담고 있는 서열입니다. 이 유전자 서열은 DNA라는 분자에 표현되어 있는데, 아시다시피 DNA를 구성하는 염기는 아데닌, 구아닌, 티민, 사이토신의 네 개밖에 없기 때문에 인간 유전자 서열은 'A', 'G', 'T', 'C' 의 네 개의 문자로만 구성됩니다.

어떤 두 인간 유전자 서열이 주어질 때, 이 두 서열 간 유사도(비슷한 정도, similarity)를 측정하고 싶습니다. 이는 다음과 같은 대응표를 참조하여 아래와 같이 정의됩니다.

table.png

  • 각 서열의 곳곳에 적당히 공백('*')을 삽입하여 같은 길이의 문자열로 만든다. 그리고 위 표에 의해, 같은 위치에 있는 두 문자들의 매칭값에 해당하는 값들을 모두 더하면 어떤 값을 얻을 수 있다. (단, 공백 끼리 매칭하는 것은 불가능하기에 표의 값이 주어져있지 않다)
  • 공백을 여러 가지 방법으로 삽입할 수 있는데, 가능한 모든 방법 중 매칭값의 합이 가장 최대가 될 때, 그 값을 유사도라고 한다.

예를 들어, 두 서열이 각각 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가 주어집니다.

T개의 테스트 케이스마다 두 개의 줄로 구성된 입력이 주어집니다.

각 줄은 서열의 길이와, 인간 유전자 서열을 담고 있습니다.

(모든 인간 유전자 서열의 길이는 100을 넘지 않는다고 합니다)

출력

각 테스트 케이스 별로, 주어진 두 인간 유전자 서열의 유사도를 출력합니다.

예제 입력

2
7 AGTGATG
5 GTTAG
7 AGCTATT
9 AGCTTTAAA

예제 출력

14
21

힌트