Shifting Paths (Large)

You have been walking in the woods for hours, and now you want to go home.

The woods contain $N$ clearings numbered $1, 2, \dots, N$. You are standing in clearing 1, and you must reach clearing $N$ to leave the woods. Each clearing from 1 to $N-1$ has one left path and one right path leading out to other clearings, and it may also have several one way paths leading in. The woods are haunted, so every time you enter a clearing, shifting trees block one of its two outgoing paths. On your $k$-th visit to a single clearing the rule is this.

• You must leave along the left path if $k$ is odd.
• You must leave along the right path if $k$ is even.
• Every path is one way, so you have no choice at any step. You must go forward through the one path that is not blocked.

So the first time you stand in clearing 1 you leave along its left path. If you come back to clearing 1 a second time you leave along its right path, and on the third visit you leave along the left path again.

You begin in clearing 1, and you leave the woods once you get to clearing $N$. How many paths do you follow before you get out?

The first line contains the number of test cases $T$. $T$ test cases follow, each beginning with a line that contains one integer $N$.

The next $N-1$ lines each contain two integers $L_i$ and $R_i$. $L_i$ is the clearing you end up at if you follow the left path out of clearing $i$, and $R_i$ is the clearing you end up at if you follow the right path out of clearing $i$.

No paths are given for clearing $N$, because you are finished once you get there.

For each test case, print one line containing "Case #x: y", where $x$ is the test case number starting from 1 and $y$ is the number of paths you follow to get to clearing $N$. If you will never get to clearing $N$, print "Infinity" in place of $y$.

• $1 \le T \le 30$
• $2 \le N \le 40$
• $1 \le L_i, R_i \le N$ for every $i$
• If you can leave the woods, the number of paths you follow is at most $10^5$.

In the first test case of the first example input, your route through the woods is the one below.