Googlander (Large)

Eric Googlander는 패션 모델이다. 그는 $R$개의 행과 $C$개의 열로 이루어진 격자 모양 무대 위를 걸어 다니며 공연한다. 처음에는 맨 아래 행의 가장 왼쪽 칸에서 무대의 위쪽 변을 바라보고 서 있고, 여기서부터 이동을 반복한다. Googlander가 할 줄 아는 이동은 다음 두 가지뿐이다.

1. 지금 바라보는 방향으로 한 칸 앞으로 간다.
2. 오른쪽으로 90도 한 번 돈 다음, 새로 바라보게 된 방향으로 한 칸 앞으로 간다.

Googlander는 왼쪽으로 90도 도는 방법을 모른다.

어떤 이동을 했을 때 무대 밖으로 나가거나 이미 지나온 칸에 들어가게 된다면, 그 이동은 촌스럽다. 두 이동이 모두 촌스럽지 않은 자리에서는 둘 중 어느 쪽이든 자유롭게 고른다. 앞에서 무엇을 골랐는지와 상관없이 매번 새로 고르지만, 반드시 하나는 골라야 한다. 두 이동 중 하나만 촌스럽다면 나머지 하나를 해야 한다. 어느 순간 두 이동이 모두 촌스러워지면 공연은 그 자리에서 바로 끝난다. Googlander는 공연을 일찍 멈추지 못한다. 두 이동이 모두 촌스러워질 때까지 계속 움직여야 한다.

Googlander가 걸을 수 있는 서로 다른 경로는 몇 가지인가? 두 경로는 같은 칸을 같은 순서로 지날 때에만 같은 경로다.

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

제한

• $1 \le T \le 100$
• $1 \le R, C \le 25$
• 이 제한에서 답은 항상 64비트 부호 있는 정수 범위에 들어간다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 Googlander가 걸을 수 있는 서로 다른 경로의 수다.

첫 번째 케이스에서 Googlander는 한 번도 움직이지 못한다. 칸 하나만 지나는 경로가 유일하다.

두 번째 케이스에서는 바라보는 방향으로 그냥 앞으로 가면 무대 밖으로 나가므로 그 이동이 촌스럽다. 대신 오른쪽으로 돌아 한 칸 갈 수 있다. 그렇게 움직인 다음에는 다시 오른쪽으로 돌아 한 칸 가는 이동이 촌스러워지고, 앞으로 한 칸 가는 이동만 남는다. 그 칸까지 가면 더 할 수 있는 이동이 없어 공연이 끝난다. 가능한 경로는 이것 하나뿐이다.

세 번째 케이스에서 가능한 경로는 다음과 같다.