제비꽃 퍼즐

퍼즐 맞추기를 좋아하시나요? 좋아하지 않아도 괜찮습니다. 이 문제에서 여러분이 할 일은 퍼즐을 직접 맞추는 것이 아니라, 퍼즐을 올바르게 맞출 수 있는 방법의 수를 세는 것입니다.

$n \times m$개의 퍼즐 조각이 주어집니다. 각 조각은 정사각형이며 네 개의 변을 가집니다. 각 변은 다음 세 가지 종류 중 하나입니다.

• 평평한 변
• 볼록 변(돌기)
• 오목 변(홈)

두 조각은 서로 맞닿는 변 중 하나가 볼록 변이고 다른 하나가 오목 변일 때에만 이어 붙일 수 있습니다(돌기가 홈에 끼워집니다). 조각은 $90^\circ$ 단위로 자유롭게 회전할 수 있지만, 뒤집을 수는 없습니다.

모든 조각이 $n \times m$ 크기의 직사각형을 이루고, 두 조각이 맞닿는 모든 곳에서 한 변은 볼록 변, 다른 한 변은 오목 변일 때 퍼즐이 올바르게 맞춰졌다고 합니다. 직사각형의 바깥 테두리에 놓인 변은 어떤 조각과도 맞닿지 않으므로, 테두리에 놓인 모든 변은 반드시 평평한 변이어야 합니다.

모든 조각의 색은 같으므로, 두 배치는 직사각형 전체에 나타나는 볼록 변과 오목 변의 배열이 서로 다를 때에만 서로 다른 것으로 봅니다. 직사각형의 방향은 고정되어 있으므로, 어떤 배치를 회전하여 다른 배치를 얻을 수 있더라도 두 배치는 서로 다른 것으로 셉니다.

올바르게 맞출 수 있는 서로 다른 방법의 수를 구하세요.

첫째 줄에 테스트의 개수 $d$ ($1 \le d \le 100$)가 주어집니다.

각 테스트는 두 정수 $n$과 $m$ ($1 \le n \le 6$, $1 \le m \le 5$)이 적힌 줄로 시작합니다. 이어지는 $n \times m$개의 줄에는 조각의 정보가 주어집니다. 각 조각은 시계 방향으로 나열한 네 변의 종류를 나타내는 네 정수로 주어지며, $0$은 평평한 변, $1$은 볼록 변(돌기), $2$는 오목 변(홈)을 뜻합니다.

각 테스트마다 올바르게 맞출 수 있는 서로 다른 방법의 수를 한 줄에 하나씩 출력하세요.

아래 그림은 한 조각 묶음을 올바르게 맞춘 한 가지 예시를 보여 줍니다.