바뀌는 경로

당신은 몇 시간 동안 숲속을 걷고 있었고, 이제 집에 가고 싶다.

숲에는 1, 2, ..., N이라는 표지가 붙은 N개의 공터가 있다. 현재 1 공터에 있으며, 숲을 빠져나가려면 N번 공터에 도달해야 한다. 1부터 N-1까지의 각 공터에는 다른 공터로 나가는 왼쪽 길과 오른쪽 길이 있고, 그 공터로 들어오는 단방향 길도 어떤 수만큼 있다. 불행히도 이 숲에는 유령이 출몰하며, 공터에 들어갈 때마다 변화무쌍한 나무들이 나가는 두 길 중 하나를 막는다. 더 정확히 말해, 어느 한 공터를 $k^{th}$번째로 방문했을 때 다음 규칙을 따른다:

• k가 홀수이면 왼쪽 길로 나가야 한다.

• k가 짝수이면 오른쪽 길로 나가야 한다.

• 모든 길은 단방향이므로 매 단계에서 선택의 여지가 없다. 막히지 않은 유일한 출구를 통해 앞으로 가야 한다. 따라서 #1 공터에 처음 있을 때는 왼쪽 길로 나간다. #1 공터에 돌아와 두 번째로 있게 된다면 오른쪽 길로 나가고, 세 번째에는 다시 왼쪽 길로 나가며, 이후에도 같은 방식으로 반복한다.

#1 공터에서 출발하며, #N 공터에 도착하면 숲을 빠져나갈 수 있다. 빠져나가기 전까지 몇 개의 길을 따라가야 하는가?

제한

메모리 제한: 1GB. 시간 제한: 테스트 세트당 30초. 1 ≤ T ≤ 30. 1 ≤ $L_{i}$, 모든 i에 대해 $R_{i}$ ≤ N.

테스트 세트 1 (Visible Verdict)

2 ≤ N ≤ 10.

테스트 세트 2 (Hidden Verdict)

2 ≤ N ≤ 40.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 하나의 정수 N이 포함된 줄로 시작한다.

이어서 N-1개의 줄이 주어지며, 각 줄에는 두 정수 $L_{i}$와 $R_{i}$가 주어진다. 여기서 $L_{i}$는 i번 공터에서 왼쪽 길을 따라 나갈 경우 도착하는 공터를 나타내며, $R_{i}$는 i번 공터에서 오른쪽 길을 따라 나갈 경우 도착하는 공터를 나타낸다.

N번 공터에 도착하면 끝나므로, N번 공터에 대해서는 경로가 주어지지 않는다.

각 테스트 케이스마다 "Case #x: y"을 한 줄에 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, y는 N번 공터에 도착하기 위해 따라가야 하는 경로의 수이다. N번 공터에 절대 도착하지 못한다면, 대신 "Infinity"을 출력한다.

Sample Explanation

첫 번째 예제 케이스에서 숲을 통과하는 경로는 아래와 같다: