구슬 잇기

격자점 위에 구슬 $2n$개가 놓여 있다. 구슬은 $n$가지 색으로 칠해져 있고 각 색마다 구슬이 정확히 2개씩이다. 구슬은 좌표 $(1,0), (2,0), \dots, (2n,0)$에 하나씩 놓인다.

색마다 같은 색 구슬 두 개를 잇는 경로를 하나씩 그린다. 각 경로는 격자점을 잇는 수평 선분과 수직 선분으로만 이루어진다. 서로 다른 두 경로는 교차하지도 맞닿지도 않는다. 어떤 경로도 직선 $y=0$을 가로지르지 못한다. 각 경로가 $y=0$과 만나는 곳은 자신이 잇는 두 구슬의 위치뿐이므로 모든 경로의 첫 선분과 마지막 선분은 수직이다.

구슬 배치가 주어지면 조건을 만족하는 경로 집합의 최소 높이를 구한다. 그릴 방법이 없으면 답은 -1이다. 높이는 경로가 지나는 점의 $y$좌표 최댓값과 최솟값의 차다.

아래 그림은 왼쪽부터 red, red, blue, yellow, blue, yellow 순서로 놓인 배치를 그린 것이다.

+---+   +-------+
|   |   |       |
R   R   B   Y   B   Y
            |       |
            +-------+

R은 red, B는 blue, Y는 yellow다. 경로가 지나는 $y$좌표는 -1부터 1까지이므로 높이는 2이고, 이보다 낮게 그릴 방법은 없다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 색의 개수 $n$이 주어진다. 다음 줄에는 구슬의 색을 왼쪽부터 순서대로 나타낸 $2n$개의 단어가 공백으로 구분되어 주어진다. 각 색 이름은 길이가 10 이하인 알파벳 소문자 문자열이다. 서로 다른 색은 정확히 $n$가지이고 각 색은 정확히 두 번 나온다.

제한

• $1 \le T \le 50$
• $1 \le n \le 20$

각 테스트 케이스마다 한 줄에 Case #x: 를 출력하고 이어서 최소 높이를 출력한다. x는 1부터 시작하는 테스트 케이스 번호다. 그릴 방법이 없으면 높이 대신 -1을 출력한다.