단백질 재활용

단백질은 아미노산이 선형 사슬 형태로 배열되어 펩타이드 결합으로 이어진 커다란 유기 분자다. 사슬을 이루는 아미노산의 종류와 그 배열 순서가 단백질의 물리적·화학적 성질을 결정한다. 표준 아미노산은 20종이며, 각각 고유한 3글자 코드로 표기한다(예: 알라닌은 Ala).

두 과학자가 아미노산 사슬을 재배열하여 한 단백질을 다른 단백질로 바꾸는 기계를 만들었다. 이를 이용하면 유기 폐기물을 인슐린 같은 유용한 물질로 바꿀 수 있다.

펩타이드 결합을 끊고 새로 만드는 화학 과정은 비용이 많이 들고, 모든 아미노산 사슬을 각각 따로 처리해야 한다. 한 아미노산 사슬을 다른 사슬로 바꾸는 데 드는 비용을 구하라.

비용은 다음과 같다.

• 사슬에서 아미노산 하나를 제거하는 비용: 2유로
• 아미노산 하나를 삽입하는 비용: 4유로
• 아미노산 하나를 다른 것으로 교체하는 비용(하나를 제거하고 그 자리에 다른 하나를 추가): 5유로

라이신(Lys), 발린(Val), 아르기닌(Arg), 히스티딘(His)은 희귀하여 더 비싸다. 이들 중 하나를 추가하거나 이들 중 하나로 교체하는 경우에는 일반 비용보다 1유로가 더 든다(즉, 희귀 아미노산을 삽입하면 5유로, 희귀 아미노산으로 교체하면 6유로). 추가할 아미노산은 얼마든지 있다고 가정한다. 두 사슬이 그 위치에서 이미 같다면, 아미노산을 그대로 두는 데에는 비용이 들지 않는다.

첫 줄에 테스트 케이스의 수를 나타내는 정수 n(0 < n ≤ 10000)이 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

• 정수 k(1 ≤ k ≤ 1000)가 있는 줄. 재활용할 사슬의 아미노산 개수다.
• k개의 줄. 각 줄에는 재활용할 사슬의 i번째 아미노산 종류를 나타내는 3글자 문자열 xi가 있다.
• 정수 m(1 ≤ m ≤ 1000)이 있는 줄. 만들고자 하는 사슬의 아미노산 개수다.
• m개의 줄. 각 줄에는 만들고자 하는 사슬의 j번째 아미노산 종류를 나타내는 3글자 문자열 yj가 있다.

한 테스트 케이스에서 서로 다른 아미노산은 최대 20종까지만 나타난다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 사슬 (x1, x2, …, xk)를 사슬 (y1, y2, …, ym)로 바꾸는 데 드는 최소 비용(유로)이다.