你已经在树林里走了好几个小时，想要回家。

树林里有 $N$ 个空地，编号为 $1, 2, \ldots, N$。你现在位于空地 1，并且必须到达空地 $N$ 才能离开树林。对于从 1 到 $N-1$ 的每个空地，都有一条左路和一条右路通向其他空地，同时还有若干条单向道路通向该空地。可惜树林被闹鬼：每当你进入一个空地时，两条出路中会有一条被狡猾的树木挡住。更准确地说，对于任意一个固定空地，当你第 $k$ 次到达它时：

• 如果 $k$ 为奇数，你必须沿左路离开。
• 如果 $k$ 为偶数，你必须沿右路离开。
• 所有道路都是单向的，因此每一步你都没有选择：你必须沿唯一未被挡住的出路继续前进。

所以你第一次在空地 #1 时，会沿左路离开。如果你后来第二次回到空地 #1，就会沿右路离开；第三次则又沿左路离开；以此类推。

你从空地 #1 出发，当你到达空地 #$N$ 时，就可以离开树林。你在离开之前需要沿道路行走多少次？

输入格式

输入第一行是测试用例数量 $T$。接下来是 $T$ 个测试用例，每个测试用例以一行整数 $N$ 开始。

接下来有 $N-1$ 行，每行包含两个整数 $L_i$ 和 $R_i$。其中，$L_i$ 表示从空地 $i$ 沿左路走会到达的空地编号，$R_i$ 表示从空地 $i$ 沿右路走会到达的空地编号。

空地 $N$ 不给出任何出路信息，因为一旦到达那里就结束了。

输出格式

对每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是到达空地 $N$ 之前需要沿道路前进的次数。如果你永远无法到达空地 $N$，则输出 "Infinity"。

限制

内存限制：1GB。

时间限制：每个测试集 30 6 秒。

$1 \le T \le 30$。

对所有 $i$，$1 \le L_i, R_i \le N$。

Test set 1 (Visible Verdict; 5 Points)

$2 \le N \le 10$。

Test set 2 (Hidden Verdict; 46 Points)

$2 \le N \le 40$。

样例数据

2
4
2 1
3 1
2 4
3
2 2
1 2

Case #1: 8
Case #2: Infinity

样例解释

在第一个样例中，你在树林中的行走路线如下表所示：