Description
Flip game is played on a rectangular N x M field with two-sided pieces placed on each of its N x M squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip some pieces, thus changing the colors of their upper sides from black to white and vice versa. The pieces to be flipped on the N x M field are chosen every round according to the following rules:
- Choose any one of the N x M pieces.
- Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any). That is, depending on the position of the chosen piece, there can be totally 3 to 5 pieces flipped.
Consider the following position as an example:
bwbw
wwww
bbwb
bwwb
Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:
bwbw
bwww
wwwb
wwwb
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.
If it's impossible, print "oops".
Input
The first line contains a single integer T (1 ≤ T ≤ 100). Then T test cases follow.
For each test case:
- The first line gives two integers N and M (1 ≤ N*M ≤ 16).
- Each of the next N lines consists of M ‘w’ or ‘b’ characters separated by spaces.
Limit:
Testcase 1: N = 1, M ≤ 4
Testcase 2: N = 1, M ≤ 16
Testcase 3: N ≤ 2, M ≤ 2
Testcase 4: N ≤ 4, M ≤ 4
Testcase 5: N ≤ 4, M ≤ 4
Output
For each test, output the minimum number of rounds to reach a winning configuration, in case such a configuration exists, or the word "oops".