Problem

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

The woods contain N clearings labeled 1, 2, ..., 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 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

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

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.

Limits

Memory limit: 1GB.

Time limit: 30 6 seconds per test set.

1 ≤ T ≤ 30.

1 ≤ L_i, R_i ≤ N for all i.

Test set 1 (Visible Verdict; 5 Points)

2 ≤ N ≤ 10.

Test set 2 (Hidden Verdict; 46 Points)

2 ≤ N ≤ 40.

Sample

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

Case #1: 8
Case #2: Infinity

Sample Explanation

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