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 kth 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?
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 Li and Ri. Here, Li represents the clearing you would end up at if you follow the left path out of clearing i, and Ri 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.
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.
1 ≤ T ≤ 30.
1 ≤ Li, Ri ≤ N for all i.
2 ≤ N ≤ 10.
2 ≤ N ≤ 40.
In the first sample case, your route through the woods will be as shown below:
|Paths followed||Clearing||Path direction|