Server Time: Fri Oct 30, 2020 4:04 am
Welcome ( logout
J - Tiles (II)
PDF (English) Ranklist
Time Limit: 4 second(s) Memory Limit: 32 MB

There is an M x N board, six types of tiles are available, and each of them is infinitely many, you have to find the number of ways you can fill the board using the tiles. Two board configurations are different if at least in one cell, their colors differ. The tiles are given below:

a1.png    a2.png    a3.png    a4.png    a5.png    a6.png

You cannot rotate or flip any tile. And no cell in the board should be empty. But some cells may be broken; you can't place any part of a tile in the broken cells. And there will be at least one cell which is not broken. The tiles shouldn't overlap.

For example, a 2 x 3 board can be colored by 5 ways, they are:

b1.png    b2.png    b3.png    b4.png    b5.png

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing two integers: M N (1 ≤ M, N ≤ 100, min(M, N) ≤ 8). Each of the next M lines contains N characters forming the board. There are two types of characters. A '.' means the cell is not broken; a '#' means the cell is broken.

Output

For each case, print the case number and the number of ways the board can be colored. The number may be large, so, output the number modulo 264.

Sample Input

Output for Sample Input

3

2 3

...

...

2 3

..#

...

5 5

.....

.....

.....

.....

.....

Case 1: 5

Case 2: 2

Case 3: 21272

 


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan