Original problem statement (in Polish) can be found here.

Bogdan the Botanist is conducting research on a certain species of plant, which supposedly have some miraculous healing properties. Thanks to his connections among other scientists, he can get as many seedlings for his research as he pleases. However, plants need proper conditions in order to grow properly.

The best method to ensure that seedlings develop correctly is to place them on specialized shelves, which have proper watering systems, lighting conditions etc. Many different shapes of the shelves are available. Apart from the standard square-shaped 1x1 shelves, it is also possible to obtain shelves that look like this:

Each of the shelves presented above consists of four standard-shaped shelves. Standard shelf can hold one large flowerpot with seedlings. Shelves presented above can hold six flowerpots, thanks to somewhat better use of available space.

Bogdan already bought a room for storing the seedlings - from birds eye view, it looks like a rectangle, n meters high and m meters wide, consisting of square-shaped fields, each 1 meter wide. You can't place the shelves on some of the fields (due to wiring, water supply systems and other stuff) - we consider such fields blocked. There is a door on the wall above the field in the top left corner - it opens inward, so we can't place anything on this field either. Bogdan plans to fit as many flowerpots in the room as possible, by placing shelves on the remaining fields. Moreover, he wants to do it in such a way that the square-shaped segments of the shelves exactly cover the fields in the room.

His research demands constant access to plants - every shelf must be accessible by walking on non-blocked fields, starting from the field with the door. You can walk between two fields if they share a common edge.

Help Bogdan! Place the shelves according to the rules, to fit as many flowerpots in the room as possible.

Input

The first line contains a single integer t, denoting the number of testcases. (t <= 10). Then, testcases follow.

The description of a single testcase begins with two integers n, m (1 <= n, m <= 50) - height and width of the rectangle representing the room. Then, n lines follow, each containing m characters. j-th character in i-th line denotes a square in i-th row nad j-th column. "." (a dot) denotes free square, "X" denotes blocked square. Field in the top left corner is always free.

Output

For every testcase you should find an arrangement of shelves that satisfies the rules from the problem statement. The descriptions begins with two integers p and d (1 <= p <= n*m) - number of shelves and number of flowerpots on the shelves, respectively. Then, the descriptions of p shelves should follow. Each shelf is described by four integers w_i, k_i, r_i and o_i (1 <= w_i <= n, 1 <= k_i <= m, 0 <= r_i <= 7, 0 <= o_i <= 3) - it means that the anchor point of the i-th shelf is in the row number w_i and column number k_i, the shelf is of type r_i, and is rotated o_i times 90 degrees to the right, starting from the configuration on the picture. Anchor point of every shape is in the top left corner in the picture (and it is in the same segment after the rotation). Type 0 denotes standard 1x1 square-shaped shelf, types from 1 to 7 correspond to shapes in the picture (counting from left to right).

Example

Input:

1
4 5
.....
....X
.X...
...X.

Output:

4 19
1 2 1 3
2 4 6 0
3 3 5 1
3 1 0 0

Explanation

The arrangement from the sample testcase looks as follows:

You can't place another shelf without violating the rules - for example, by putting type 0 shelf on the field at (2,3), the red shelf and the green shelf would be unreachable. The arrangement contains three larger shelves and one standard shelf, so the total number of flowerpots is 3*6+1 = 19.

Scoring

If the arrangement of the shelves is correct, and the given number of flowerpots d is correct, it is worth d/(n*m) points. Overall score is equal to the sum of individual scores. Score for the sample output is 19/(4*5) = 0.95.