음양의 길 (Large)

$N$행 $M$열 격자의 각 칸을 검은색(음) 또는 흰색(양)으로 칠한다. 두 칸이 길이가 1인 변을 공유하면 이웃이라고 한다. 검은 칸 전체가 하나의 경로를 이루고 흰 칸 전체도 하나의 경로를 이루면 그 격자를 유효한 격자라고 한다. 칸의 집합 $S$가 경로라는 것은 다음 세 조건을 모두 만족한다는 뜻이다.

• $S$는 연결되어 있다. $S$의 어느 칸에서 출발하든 $S$ 안의 이웃만 거쳐 $S$의 나머지 칸에 모두 도달한다.
• $S$ 안에서 이웃이 정확히 하나인 칸이 정확히 두 개 있다. 이 두 칸을 경로의 끝이라고 한다.
• 나머지 칸은 모두 $S$ 안에서 이웃이 정확히 둘이다.

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

$N$과 $M$이 주어질 때 유효한 격자가 몇 개인지 구한다. 회전하거나 뒤집어서 겹치는 두 격자라도 한 칸이라도 색이 다르면 서로 다른 격자로 센다.

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

각 테스트 케이스마다 Case #x: A 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $A$는 주어진 크기에서 유효한 격자의 개수이다.

• $1 \le T \le 50$
• $4 \le N, M \le 14$