움직이는 길 (작은 문제)

몇 시간째 숲을 헤매다가 이제 집으로 돌아가려 한다.

숲에는 $1$번부터 $N$번까지 번호가 붙은 빈터가 $N$개 있다. 지금 서 있는 곳은 $1$번 빈터이고, $N$번 빈터에 도착해야 숲을 빠져나갈 수 있다. $1$번부터 $N-1$번까지의 빈터에는 밖으로 나가는 왼쪽 길과 오른쪽 길이 하나씩 있고, 안으로 들어오는 일방통행 길이 여러 개 있을 수 있다.

숲의 나무는 자리를 옮겨 다니면서 길을 막는다. 어떤 빈터에 $k$번째로 들어왔다면 다음 규칙을 따른다.

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

모든 길은 일방통행이고 나가는 두 길 중 하나만 열려 있으므로, 각 빈터에서 고를 여지는 없다. 열린 길을 그대로 따라가야 한다.

예를 들어 $1$번 빈터에 처음 섰을 때는 왼쪽 길로 나간다. $1$번 빈터로 다시 돌아오면 그때는 오른쪽 길로 나가고, 세 번째로 돌아오면 다시 왼쪽 길로 나간다.

$1$번 빈터에서 출발해 $N$번 빈터에 닿을 때까지 따라가야 하는 길의 개수를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 정수 $N$이 주어진다. 이어지는 $N-1$개의 줄 중 $i$번째 줄에는 두 정수 $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 10$
• $1 \le L_i, R_i \le N$

첫 번째 예제의 첫 테스트 케이스에서 숲을 빠져나가는 경로는 다음과 같다.