Description

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

The woods contain $N$ clearings labeled $1, 2, \dots, N$. You are now at clearing $1$, and you must reach clearing $N$ in order to leave the woods. Each clearing from $1$ to $N-1$ has a left path and a right path leading out to other clearings, as well as some number of one-way paths leading in. Unfortunately, the woods are haunted, and any time you enter a clearing, one of the two outgoing paths will be blocked by shifty trees. More precisely, on your $k^{th}$ visit to any single clearing:

• You must leave along the left path if $k$ is odd.
• You must leave along the right path if $k$ is even.
• All paths are one-way, so you have no choice at each step: you must go forward through the one unblocked outgoing path.

So the first time you are in clearing #1, you will leave along the left path. If you ever come back to clearing #1 for a second time, you would leave along the right path; the third time, you'd leave along the left path again; and so on.

You begin at clearing #1, and when you get to clearing #N, you can leave the woods. How many paths do you need to follow before you get out?

Input Format

The first line of the input gives the number of test cases, $T$. $T$ test cases follow, each beginning with a line containing a single integer $N$.

$N-1$ lines follow, each containing two integers $L_i$ and $R_i$. Here, $L_i$ represents the clearing you would end up at if you follow the left path out of clearing $i$, and $R_i$ represents the clearing you would end up at if you follow the right path out of clearing $i$.

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

Output Format

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

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

Case #1: 8
Case #2: Infinity

Hint

Sample Explanation

In the first sample case, your route through the woods will be as shown below:

Limits

• $1 \leq T \leq 30.$
• $1 \leq L_i, R_i \leq N$ for all $i$.

Test set 1 (5 Pts, Visible Verdict)

• $2 \leq N \leq 10.$

Test set 2 (46 Pts, Hidden Verdict)

• $2 \leq N \leq 40.$