You have been walking in the woods for hours, and you want to go home.
The woods contain clearings labeled . You are now at clearing , and you must reach clearing in order to leave the woods. Each clearing from to 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 visit to any single clearing:
You must leave along the left path if is odd.
You must leave along the right path if 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?
输入格式
The first line of the input gives the number of test cases, . test cases follow, each beginning with a line containing a single integer .
lines follow, each containing two integers and . Here, represents the clearing you would end up at if you follow the left path out of clearing , and represents the clearing you would end up at if you follow the right path out of clearing .
No paths are specified for clearing because once you get there, you are finished.
输出格式
For each test case, output one line containing "Case #: ", where is the case number (starting from 1) and is the number of paths you need to follow to get to clearing . If you will never get to clearing , output "Infinity" instead.
样例
样例输入 1
2
4
2 1
3 1
2 4
3
2 2
1 2
样例输出 1
Case #1: 8
Case #2: Infinity
数据范围与提示
Sample Explanation
In the first sample case, your route through the woods will be as shown below:
