구슬

정사각 격자 위에 2n개의 구슬이 있다. 구슬은 n가지 서로 다른 색으로 칠해져 있으며, 각 색의 구슬은 정확히 2개씩 있다. 구슬은 좌표 (1,0), (2,0), ..., (2n, 0)에 놓여 있다.

각 색에 대해 그 색의 두 구슬을 잇는 경로를 그려야 한다. 각 경로는 격자점 사이를 잇는 수직 또는 수평 선분으로 구성되어야 한다. 어떤 두 경로도 서로 교차하거나 맞닿을 수 없다. 어떤 경로도 y=0 직선을 가로지를 수 없다. 각 경로는 연결하는 두 구슬의 위치에서만 y=0 직선에 맞닿을 수 있으므로, 각 경로의 첫 선분과 마지막 선분은 수직이어야 한다.

구슬의 배치가 주어질 때, 해의 최소 높이를 반환하거나 해가 존재하지 않으면 -1을 반환한다. 높이는 사용된 경로의 Y좌표 중 가장 높은 것과 가장 낮은 것의 차이로 정의한다.

예제:

red red blue yellow blue yellow

한 가지 해는 다음과 같다:

+---+    +-----------+
 |   |    |           |
red red blue yellow blue yellow
                 |           |
                 +-----------+

이 경우 최소 높이는 2이다.

제한

메모리 제한: 1 GB. 1 <= T <= 50.

작은 데이터 세트

시간 제한: 30초. 1 <= n <= 20.

큰 데이터 세트

시간 제한: 60초. 1 <= n <= 500.

입력의 첫 줄에는 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 케이스의 첫 줄에는 구슬의 서로 다른 색의 수 n이 주어진다. 다음 줄에는 왼쪽에서 오른쪽 순서로 구슬의 색에 대응하는 2n개의 단어가 공백으로 구분된 문자열이 주어진다. 각 색은 소문자('a' .. 'z')로 이루어진 길이가 10자를 넘지 않는 문자열이다. 서로 다른 색은 정확히 n가지이며, 각 색은 정확히 두 번 나타난다.

각 테스트 케이스마다 "Case #x: "을 포함하는 한 줄을 출력한다. 여기서 x는 (1부터 시작하는) 케이스 번호이며, 그 뒤에 임의의 최적해의 높이를 출력하거나 해가 존재하지 않으면 -1을 출력한다.