有一天，Little Apple 在纸上画了一棵树，并写下了这棵树的 DFS（深度优先搜索）序列和 BFS（广度优先搜索）序列。几天后，他想知道他画的那棵树的直径。遗憾的是，画着树的纸丢了。他只记得这棵树的 DFS 序列和 BFS 序列，因此他想知道这棵树直径的期望长度。然而，他不知道该如何计算。作为一名优秀的程序员，请你帮帮他。

假设 $S$ 是树的顶点集。两个顶点 $u, v$ 之间的距离是 $u$ 和 $v$ 之间最短路径的长度（以边数为单位）。树的直径等于：

$$\max\{\text{dist}(u, v) \mid u, v \in S\}$$

其中 $\text{dist}(u, v)$ 表示顶点 $u$ 和 $v$ 之间的距离。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 10000$)，表示树的顶点数。接下来有两行。第一行包含 $n$ 个整数，表示树的 DFS 序列。第二行包含 $n$ 个整数，表示树的 BFS 序列。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是树的直径的期望值。

如果你的答案与正确答案的绝对误差在 $10^{-4}$ 以内，则视为正确。

样例

输入 1

1
7
1 2 3 5 4 7 6
1 2 4 6 3 5 7

输出 1

Case #1: 4.000