Marbles

A square grid holds $2n$ marbles. They are painted in $n$ colors with exactly two marbles of each color, and they sit at the coordinates $(1, 0), (2, 0), \dots, (2n, 0)$, one marble per point.

For each color, draw one path that joins the two marbles of that color. A path is made of vertical and horizontal segments between grid points. No two paths may cross or touch each other. No path may cross the line $y = 0$, and a path may touch $y = 0$ only at the two marbles it joins, so the first and the last segment of every path is vertical.

Given the arrangement of the marbles, find the smallest height of a drawing that obeys these rules. When no such drawing exists the answer is -1. The height is the difference between the largest and the smallest $y$ coordinate over the points of the drawn paths.

Figure. With the marbles in the order red red blue yellow blue yellow, the drawing below has height 2. R is red, B is blue, and Y is yellow.

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

The first line contains the number of test cases $T$. The first line of each test case contains $n$, the number of colors. The next line contains the colors of the marbles from left to right, $2n$ words separated by spaces. Each color is a string of at most 10 lowercase English letters. Exactly $n$ different colors appear and each color appears exactly twice.

Limits

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

For each test case, print Case #x: followed by the smallest height, one test case per line. x is the test case number starting from 1. Print -1 instead of a height when no valid drawing exists.