Marbles

You have $2n$ marbles on a square grid. The marbles come in $n$ colors and there are exactly 2 marbles of each color. 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. Every path is built from horizontal and vertical segments between grid points. No two paths intersect or touch each other. No path crosses the line $y=0$. A path meets $y=0$ only at the two marbles it connects, so the first and the last segment of every path is vertical.

Given an arrangement of marbles, report the minimum height over all valid sets of paths. If no valid set exists, the answer is -1. The height is the difference between the largest and the smallest $y$ coordinate that the paths reach.

The picture below draws the arrangement red, red, blue, yellow, blue, yellow from left to right.

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

R is red, B is blue, and Y is yellow. The paths reach $y$ coordinates from -1 to 1, so the height is 2, and no drawing is lower.

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

Limits

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

For each test case, print one line holding Case #x: followed by the minimum height. x is the case number, starting from 1. When no valid set of paths exists, print -1 in place of the height.