음양의 경로

N개의 행과 M개의 열로 이루어진 직사각형 격자가 주어지며, 각 칸은 검은색(Yin) 또는 흰색(Yang)으로 표시할 수 있다. 두 칸이 공통된 단위 길이의 변을 공유하면 이웃한다. 모든 검은색 칸이 하나의 경로를 이루고 모든 흰색 칸이 하나의 경로를 이루면 격자는 유효하다. 경로란 다음과 같이 정의되는 칸의 집합 S이다.

• 칸들은 하나의 연결된 조각을 이룬다. S의 각 칸에서 이웃한 칸 사이를 S 내부에서 이동하여 S의 다른 어떤 칸에도 도달할 수 있다.

• S에 속한 정확히 두 칸은 각각 S에서 정확히 하나의 이웃을 갖는다. 이 칸들이 경로의 "ends"이다.

• S에 속한 나머지 모든 칸은 S에서 정확히 두 개의 이웃을 갖는다.

예를 들어 아래 그림에서 첫 번째 격자는 유효하지만 두 번째 격자는 유효하지 않다. 검은색 칸들은 경로를 이루지만 흰색 칸들은 경로를 이루지 않기 때문이다.

N과 M이 주어질 때 유효한 격자의 수를 계산한다. 대칭 여부는 중요하지 않다는 점에 유의한다. 두 유효한 격자가 한 위치라도 다르면, 하나를 회전하거나 뒤집어 다른 하나로 만들 수 있더라도 서로 다른 것으로 간주한다.

제한

메모리 제한: 1GB. 1 ≤ T ≤ 50

소규모 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 테스트 세트당 30초. 4 ≤ N, M ≤ 10

대규모 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 테스트 세트당 120초. 테스트 케이스 중 80%에서는 4 ≤ N, M ≤ 50 테스트 케이스 중 90%에서는 4 ≤ N, M ≤ 70 모든 테스트 케이스에서 4 ≤ N, M ≤ 100

입력의 첫 줄에는 테스트 케이스의 수인 정수 T 하나가 주어진다. 이어서 T개의 줄이 주어지며, 각 줄에는 위에서 정의한 두 정수 "N M"가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 "Case #x: A" 형식으로 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, A는 지정된 크기의 유효한 격자 수이다.