구슬 잇기

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

색마다 같은 색 구슬 두 개를 잇는 경로를 하나씩 그려야 한다. 경로는 격자점을 잇는 수직 선분과 수평 선분으로만 이루어진다. 두 경로는 서로 교차하거나 닿을 수 없다. 어떤 경로도 직선 $y = 0$을 넘어갈 수 없고, 자신이 잇는 두 구슬의 자리에서만 $y = 0$에 닿을 수 있다. 그래서 모든 경로의 첫 선분과 마지막 선분은 수직이다.

구슬의 배치가 주어지면 조건을 만족하는 그림의 높이 중 최솟값을 구하라. 조건을 만족하는 그림이 없으면 -1이다. 높이는 그려진 경로에 속한 점의 $y$좌표 중 최댓값과 최솟값의 차다.

그림. 구슬이 red red blue yellow blue yellow 순서로 놓인 경우, 아래처럼 그리면 높이가 2다. R은 red, B는 blue, Y는 yellow다.

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

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

제한

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

각 테스트 케이스마다 Case #x: 를 출력하고 이어서 높이의 최솟값을 출력한다. 한 테스트 케이스가 한 줄이다. x는 1부터 시작하는 테스트 케이스 번호다. 조건을 만족하는 그림이 없으면 높이 대신 -1을 출력한다.