You are given a grid of row r and column c. The rows are numbered from 0 to r − 1 and columns are numbered from 0 to c − 1. A node in row i and column j can have edge with nodes at position (i − 1, j), (i,j−1),(i+1,j)and(i,j+1). Nowforthegivengridsomeofitsedgeisgiven. Youcanaddsome other edge in the grid. You have to add the edges in such a way so that all the nodes in the grid are connected but do not create any cycle. You have to count the number of ways that you can add edges in the grid. Input First line contains T (1 ≤ T ≤ 30) the number of test cases. Then T test cases follow. First line of each test case contain 3 integer r (1 ≤ r ≤ 200),c (1 ≤ c ≤ 8) and md (1 ≤ md ≤ 1000000). Next 2 ∗ r − 1 line contains the description of the maze. Each of these line contains 2 ∗ c − 1 character. Each of the even number column of the even number row will be a ‘.’ denoting the node. Each of the odd number column of the even number row will either be a space denoting that there is no edge between the adjacent vertices or a ‘-’ character denoting there is an edge. Each of the even number column of the odd number rows can be single ‘|’ denoting there is a vertical edge or a single space denoting there is no edge there. See the sample input for further clarification. Note in the sample input the spaces are replaced by S for readability. In the original input file they will be spaces. Output For each test case output the number of ways you can add edges to the grid so that the grid is connected and form a tree. This result may be large. So output result%md. In the case the existing edges already creates a cycle output A line containing ‘Impossible’ without the quotes. Sample Input 6 2 2 1000 .S. SSS .S. 2 2 100 .-. |S| .S. 2 2 100 .-. |S| .-. 3 3 10000 .S.S. SSSSS .S.S. SSSSS .S.S.
2/2 3 3 10000 .-.-. SSSSS .-.-. SSSSS .-.-. 3 3 10000 .S.S. |S|S| .S.S. |S|S| .S.S. Sample Output 4 1 Impossible 192 9 9