움직이는 숲길 (Large)

숲속을 몇 시간이나 걸었고, 이제 집으로 돌아가려 한다.

숲에는 $1, 2, \dots, N$번으로 번호가 붙은 빈터 $N$개가 있다. 지금 1번 빈터에 있고, 숲을 벗어나려면 $N$번 빈터에 도착해야 한다. 1번부터 $N-1$번까지의 빈터에는 각각 다른 빈터로 나가는 왼쪽 길과 오른쪽 길이 하나씩 있고, 들어오는 일방통행 길도 여러 개 있을 수 있다. 그런데 이 숲에는 귀신이 붙어 있어서, 어떤 빈터에 들어설 때마다 나가는 두 길 중 하나가 움직이는 나무에 막힌다. 어떤 빈터를 $k$번째로 방문한 경우 규칙은 이렇다.

• $k$가 홀수면 왼쪽 길로 나가야 한다.
• $k$가 짝수면 오른쪽 길로 나가야 한다.
• 모든 길은 일방통행이라 매 순간 선택의 여지가 없다. 막히지 않은 길 하나로 나아가야 한다.

즉 1번 빈터에 처음 서 있을 때는 왼쪽 길로 나간다. 나중에 1번 빈터로 두 번째로 돌아오면 오른쪽 길로 나가고, 세 번째로 돌아오면 다시 왼쪽 길로 나간다.

1번 빈터에서 출발해 $N$번 빈터에 도착하면 숲을 벗어난다. 벗어나기까지 길을 몇 번 지나야 하는지 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어지고, 각 테스트 케이스의 첫 줄에는 정수 $N$이 있다.

다음 $N-1$개의 줄에는 두 정수 $L_i$와 $R_i$가 주어진다. $L_i$는 $i$번 빈터에서 왼쪽 길로 나갔을 때 도착하는 빈터의 번호이고, $R_i$는 오른쪽 길로 나갔을 때 도착하는 빈터의 번호다.

$N$번 빈터에 도착하면 그대로 끝나므로, $N$번 빈터의 길은 주어지지 않는다.

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 $N$번 빈터에 도착하기까지 지나는 길의 개수다. $N$번 빈터에 절대 도착할 수 없으면 $y$ 자리에 "Infinity"를 출력한다.

• $1 \le T \le 30$
• $2 \le N \le 40$
• 모든 $i$에 대해 $1 \le L_i, R_i \le N$
• 숲을 벗어날 수 있다면, 지나는 길의 개수는 $10^5$ 이하다.

첫 번째 예제 입력의 첫 테스트 케이스에서 따라가게 되는 경로는 다음과 같다.