It is quite easy to draw regular polygons but what about regular polyhedron? If you are allowed to cut papers and join them to form regular polyhedron it would be easy task, but what if I tell you to fold papers to form polyhedron? Let me clear you by a picture excerpt from Wikipedia. Left side paper can be folded to form an octahedron. If you don’t know how an octahedron looks like, it is shown in the right side. However you don’t need to be scared seeing the octahedron. We will work with the simplest of all polyhedron, regular hexahedron. Actually regular hexahedron is formal name of cube. Let’s look at the following pictures: Left side paper can be folded to a cube. There are many other shapes of six connected squares which can be folded to form a cube. In this problem you will be given a grid. It will be a R × C rectangle which is divided into unit squares. A square will look like one of the following: So a 2 × 2 grid may look the left diagram below (which as input to your program will be given as right one. You will find the meaning of the numbers in the above picture):
2/2 In how many ways can you cut 6 connected squares from the given R × C grid so that when a cube is formed folding them, the lines on the cube surfaces form a single loop? For example, if we cut out the left portion from a grid in the diagram below it will form a valid cube, but if we cut out the right portion, we can fold it to form a cube but the lines on the surfaces will not form a single loop. So it is not valid. Note that, the lines on the grid are in both sides and the lines in both the sides are same. So you don’t need to worry which side of the grid square is inside cube. Input First line of the test case contains a positive integer T (T ≤ 100). Hence follows T test cases. Each test case starts with 2 positive integer R and C denoting number of rows and number of columns in grid respectively (1 ≤ R, C ≤ 20). Then there will be R lines of C integers. Each integer will range from 0 to 5 (meaning of each of the number is given in the problem statement). Output For each case, output the case number followed by the answer to the query in the problem description. Sample Input 3 34 0030 3150 0030 34 0034 3150 0032 34 0030 2453 0020 Sample Output Case 1: 1 Case 2: 4 Case 3: 0