Googlander

Eric Googlander는 R개의 행과 C개의 열로 이루어진 격자 모양의 정사각형 무대 위를 걸어 다니며 공연하는 패션 모델이다. 그는 맨 왼쪽 아래 칸에서 무대의 위쪽 가장자리를 바라보며 시작하고, 일련의 이동을 하며 공연한다. Googlander가 아는 이동은 다음 두 가지뿐이다:

1. 현재 바라보는 방향으로 한 걸음 앞으로 간다

2. 오른쪽으로 한 번 90도 회전한 뒤, 회전 후 새롭게 바라보는 방향으로 한 걸음 앞으로 간다

(Googlander는 왼쪽으로 90도 회전하는 방법을 모른다는 점에 유의하라.)

어떤 이동으로 인해 Googlander가 무대 밖으로 나가거나 이미 방문한 칸으로 가게 된다면, 그 이동은 유행에 맞지 않는다. Whenever Googlander가 가능한 두 이동 중 어느 것도 유행에 맞지 않는 이동이 아닌 위치에 있다면, (과거에 했던 다른 모든 선택과 독립적으로) 둘 중 어느 이동이든 자유롭게 선택할 수 있지만 반드시 하나를 선택해야 한다. 가능한 이동 중 하나가 유행에 맞지 않을 때마다 다른 이동을 해야 한다. 어느 시점에 가능한 두 이동이 모두 유행에 맞지 않으면, Googlander는 더 이동하지 않고 공연이 즉시 끝난다. Googlander는 공연을 일찍 끝낼 수 없으며, 가능한 두 이동이 모두 유행에 맞지 않게 될 때까지 계속 이동해야 한다는 점에 유의하라.

Googlander가 걸을 수 있는 서로 다른 경로는 몇 개인가? (두 경로가 같은 순서로 같은 칸들을 방문할 때, 그리고 그럴 때에만 두 경로는 같다.)

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ R, C ≤ 10. 제한에 따라 답은 항상 32-비트 부호 있는 정수에 들어간다.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ R, C ≤ 25. 제한에 따라 답은 항상 64-비트 부호 있는 정수에 들어간다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어지는 T개의 줄에는 각각 공백으로 구분된 두 정수 R과 C가 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 Googlander가 걸을 수 있는 서로 다른 경로의 수이다.

케이스 #1에서 Googlander는 어떤 이동도 할 수 없다. 가능한 유일한 경로는 유일한 칸 하나로만 이루어진 자명한 경로이다.

케이스 #2에서 Googlander는 똑바로 앞으로 한 걸음 가면 무대 밖으로 나가므로 그렇게 이동할 수 없지만, 오른쪽으로 회전한 뒤 한 걸음 갈 수 있다. 그렇게 하고 나면 오른쪽으로 회전한 뒤 한 걸음 갈 수 없지만, 똑바로 앞으로 한 걸음 갈 수 있다. 그 시점에는 더 이상 가능한 이동이 없으므로 공연이 끝난다. 이것이 그가 택할 수 있는 유일한 경로이다.

케이스 #3에서 가능한 경로는 다음과 같다: