This page is still under construction.

Parts of this page are still being built. What you see may change.

Violet Jigsaw Puzzle

Time limit5sMemory limit128 MB

Summary
Count how many ways to place and rotate the given pieces into an n by m rectangle so that all touching sides match tab-to-blank and border sides are flat.
Level

Medium7 of 10

Topics
Backtracking, Implementation, Bit manipulation
Solved
No attempts yet

Problem

Do you like assembling jigsaw puzzles? Even if you do not, that is fine. In this problem your task is not to assemble the puzzle yourself, but to count how many different correct assemblies are possible.

You are given n×mn \times m puzzle pieces. Each piece is a square with four sides. Every side is one of three kinds:

  • a flat side,
  • a tab (a bump that sticks out),
  • a blank (an indentation, a hole).

Two pieces may be joined along a shared side only if one of the two touching sides is a tab and the other is a blank (the tab fits into the blank). Pieces may be rotated freely by multiples of 90∘90^\circ, but may not be flipped over.

The pieces are assembled correctly when they form an n×mn \times m rectangle and, at every place where two pieces meet, one side is a tab and the other is a blank. A side lying on the outer border of the rectangle touches no other piece, so every border side must be flat.

All pieces have the same color, so two assemblies are considered different only when the pattern of tabs and blanks over the whole rectangle differs. The orientation of the rectangle is fixed, so two assemblies are counted as different even if one can be obtained by rotating the other.

Count the number of different correct assemblies.

Input

The first line contains the number of tests dd (1≤d≤1001 \le d \le 100).

Each test begins with a line containing two integers nn and mm (1≤n≤61 \le n \le 6, 1≤m≤51 \le m \le 5). The next n×mn \times m lines describe the pieces. Each piece is given by four integers listing the kinds of its four sides in clockwise order, where 00 is a flat side, 11 is a tab, and 22 is a blank (hole).

Output

For each test, print on its own line the number of different correct assemblies.

Note

The figure below shows one correct way to assemble a set of pieces.

An example of a correctly assembled puzzle

Examples4

  1. Example 1

    Input
    2
3 3
0 0 1 2
0 0 1 2
0 0 1 2
0 0 1 2
0 1 1 2
0 1 1 2
0 1 1 2
0 1 1 2
2 2 2 2

3 3
0 0 1 2
0 0 1 2
0 0 1 2
0 0 1 2
0 1 1 2
0 1 1 2
0 1 1 2
0 1 2 2
2 2 2 2
    Expected output
    1
0

  2. Example 2

    Input
    2
1 1
0 0 0 0
1 1
0 0 0 1
    Expected output
    1
0

  3. Example 3

    Input
    1
1 2
0 0 0 1
0 0 0 2
    Expected output
    2

  4. Example 4

    Input
    1
2 2
0 0 1 2
0 0 1 2
0 0 1 2
0 0 1 2
    Expected output
    1