MatScan

Time Limit: 1 Second Memory Limit: 32768 KB
Special Judge

Background:

Manager (M): Hey, bob, you got the manual of the new Advance Cell Matrix scanner?

Bob (B): Yeah. This machine is exciting. It can scan either horizontally or vertically in one session comparing our old machine that can do only spot test in a run. This new buddy can boost our test period like rocket.

M: When do you estimate your data can be proceeded then? I assume with the new machine you can cheer up our boss by the end of this month?

B: Hmm, I will do my best, in case he promise me a bonus. But currently I am not sure how good it can really until i run some serious tests on it.

M: Oh, really? This machine is quite expensive so I hope it can just work as it was advertised.

B: Don't worry, I will configure the machine before we run and make sure the time consumed is optimized.

M: That sounds good. Look, if you work well on this machine and by the end of this year you may be sitting in my desk.

B: And you?

M: CEO, probably.

B: ...

Bob surely wants to be the manager (and later CEO, since an ACM that can scan two directions in one session may occur soon), so you, his poor assistant must figure out the way to optimize the scan session so the time consumed is minimized. You want Bob's position, when he is gone, right?

Input

One integer in the first line, followed by a blank line, stating the number of test cases. There will be no more than 1024 tests.

For each test case, the first line is two integer 'rows', 'cols' (1 <= rows, cols <= 100) stating the number of rows and columns of the matrix respectively. Then 'rows' lines follow each with 'cols' characters describing the matrix. A '*' is a grid of interest and your scan line must cover it at least once. A '.' is a grid ignorable so to save time, you probably do not want to scan it. A scan goes through the matrix along its direction and can not be interrupted. All sessions take a same unit time.

The test cases will be separated by a single blank line.

Output

An integer reporting the optimum unit time used to finish the scan that covers all grids of interest. That many lines follow describing the detail of the configuration with 2 integers in each line, 'd' and 'k', with no leading or trailing spaces and separated with a single space. The integer 'd' is the direction to scan, for which '1' stands for horizontal scan in row direction and '2' stands for vertical scan in column direction. 'k' is the row id or column id, depending on the direction scanned as stated with 'd'. The row number is between 1 and 'rows' inclusive and the column number is between 1 and 'cols' inclusive.

All valid answer within the optimum time we expect will be accepted.

Use a single blank line to separate neighboring output blocks.

Sample Input

2

4 4
.**.
.**.
..*.
.*..

1 1
*

Sample Output

Submit

Source: ZOJ 3rd Anniversary Contest