Shifting Paths (Small)

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

The woods contain $N$ clearings numbered $1$ to $N$. You are standing in clearing $1$, and you leave the woods only when you reach clearing $N$. Every clearing from $1$ to $N-1$ has one left path and one right path leading out of it, plus any number of one way paths leading in.

The trees shift and block paths. On your $k$-th visit to a clearing:

• you must leave along the left path when $k$ is odd,
• you must leave along the right path when $k$ is even.

Every path is one way and only one of the two outgoing paths is open, so you never have a choice at a clearing. You must follow the open path.

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

Count the paths you have to follow to get from clearing $1$ to clearing $N$.

The first line contains the number of test cases $T$.

Each test case begins with a line containing one integer $N$. The next $N-1$ lines follow, and line $i$ contains two integers $L_i$ and $R_i$. Here $L_i$ is the clearing you arrive at after leaving clearing $i$ along the left path, and $R_i$ is the clearing you arrive at after leaving it along the right path.

No paths are given for clearing $N$ because the walk ends there.

For each test case, print one line in the form "Case #x: y", where $x$ is the test case number starting from $1$ and $y$ is the number of paths you follow to reach clearing $N$.

If you never reach clearing $N$, print "Infinity" in place of $y$.

• $1 \le T \le 30$
• $2 \le N \le 10$
• $1 \le L_i, R_i \le N$

In the first test case of the first example, the route out of the woods is the following.