모두 바꾸기

Banana Rocks Inc는 일반적인 편집 연산인 "모두 바꾸기"를 구현하는 혁신적인 기술을 개발하고 있다. 이 구현은 주어진 텍스트에서 특정 문자가 나타나는 모든 자리를 다른 문자로 바꾼다. 텍스트에 그 문자가 없으면 연산은 수행되지만 아무 효과가 없다. 예를 들어 시작 텍스트가 CODEJAMWORLDFINALS일 때 A를 O로 바꾸면 새 텍스트는 CODEJOMWORLDFINOLS가 된다. 이 결과에 O를 Y로 바꾸는 연산을 다시 수행하면 최종 텍스트는 CYDEJYMWYRLDFINYLS가 된다. 구현이 아직 완성되지 않아 목록에 있는 N개의 문자 쌍에 대해서만 바꾸기를 수행할 수 있다. 문자 c1을 c2로 바꾸는 기능이 구현되어 있더라도, c2를 c1으로 바꾸는 반대 기능은 구현되어 있을 수도 있고 없을 수도 있다. 초기 문자열 S에서 시작해 바꾸기를 원하는 횟수만큼 순서대로 수행할 수 있다. 첫 번째 바꾸기는 S에 적용하고, i+1번째 바꾸기는 i번째 바꾸기의 결과에 적용한다. 구현된 바꾸기를 모두 최소 한 번씩 수행해야 한다는 것이 유일한 조건이다. 각 바꾸기의 횟수에는 상한이 없다. 사용할 수 있는 문자는 숫자와 영문 대소문자이며, 같은 글자의 대문자와 소문자는 서로 다른 문자로 취급한다. 마지막 바꾸기를 수행한 결과인 텍스트에 나타날 수 있는 서로 다른 문자의 최대 개수는 얼마인가?

첫 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 초기 텍스트 S와 구현된 바꾸기의 수 N이 주어진다. 둘째 줄에는 두 글자짜리 문자열 R1, R2, ..., RN이 주어지며, 각각이 구현된 바꾸기를 나타낸다. Ri의 첫 번째 글자는 Ai, 두 번째 글자는 Bi이고, i번째 바꾸기는 Ai가 나타나는 모든 자리를 Bi로 바꾼다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 구현된 모든 바꾸기를 S에 각각 한 번 이상, 어떤 순서로든 수행한 결과 텍스트에 나타날 수 있는 서로 다른 문자의 최대 개수이다.

$1 \le T \le 100$이다. 모든 $i$에 대해 $2 \le |S| \le 1000$이다. S의 각 문자는 영문 대문자, 영문 소문자, 또는 숫자이다. 모든 $A_i$와 $B_i$도 영문 대문자, 영문 소문자, 또는 숫자이다. 모든 $i$에 대해 $A_i \ne B_i$이다. 모든 $i \ne j$에 대해 $(A_i, B_i) \ne (A_j, B_j)$이다. 즉 각 바꾸기는 서로 달라야 한다.

바꾸기 목록의 문자는 초기 텍스트에 나타나지 않을 수 있고, 초기 텍스트의 문자는 구현된 바꾸기 목록에 없을 수도 있다. 대문자 B와 소문자 b는 서로 다른 문자이다.