你有 $2n$ 个弹珠放置在方格网格上。这些弹珠共有 $n$ 种不同的颜色，每种颜色恰好有两个弹珠。弹珠被放置在坐标 $(1,0), (2,0), \dots, (2n, 0)$ 处。

你的任务是为每种颜色画一条路径，连接该颜色的两个弹珠。每条路径应由网格点之间的垂直或水平线段组成。任意两条路径不得相交或接触。任何路径不得穿过 $y=0$ 线。每条路径仅能在其连接的两个弹珠的位置接触 $y=0$ 线，因此每条路径的第一条和最后一条线段必须是垂直的。

给定弹珠的排列，返回解的最小高度；如果不存在解，则返回 -1。高度定义为路径所使用的最高 $Y$ 坐标与最低 $Y$ 坐标之差。

示例：

red red blue yellow blue yellow

一种解法如下：

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

在这种情况下，最小高度为 2。

输入

输入的第一行包含测试用例的数量 $T$。 接下来是 $T$ 个测试用例。每个测试用例的第一行包含 $n$，即弹珠颜色的数量。下一行包含一个由 $2n$ 个单词组成的字符串，单词之间用空格分隔，对应于从左到右排列的弹珠颜色。每种颜色是一个长度不超过 10 个字符的小写字母字符串（'a' .. 'z'）。共有 $n$ 种不同的颜色，每种颜色恰好出现两次。

输出

对于每个测试用例，输出一行 "Case #$x$: "，其中 $x$ 是测试用例编号（从 1 开始），后跟最优解的高度，如果不存在解，则输出 -1。

样例

输入格式 1

4
3
red red blue yellow blue yellow
3
red blue yellow red blue yellow
3
red blue yellow blue yellow red
3
red red blue blue yellow yellow

输出格式 1

Case #1: 2
Case #2: -1
Case #3: 3
Case #4: 1