A little known fact is that cats really love solving captchas! Today, Mimi the cat has prepared some captcha puzzles by drawing digits out of asterisks.
The numbers are drawn as follows:
Mimi can scale the numbers up and down by adding or removing asterisks from each edge. For example, the following are all the number 0:
-*- *-* *-* --- *-* *-* -*-
-*-*- *---* ----- *---* -*-*-
-*-*-*- *-----* *-----* *-----* ------- *-----* *-----* *-----* -*-*-*-
Note that all horizontal segments are of the same length, and all vertical segments are of the same length. Mimi may also add additional dashes as padding around the digits. Note that the padding can include extra lines consisting only of dashes before and after the actual number.
Mimi just has one little problem - she needs someone else to make sure she solved her puzzles correctly! Can you help your good friend Mimi?
The first line begins with a single integer ~T~ ~(1 \le T \le 10)~, the number of test cases. ~T~ test cases follow.
Each test case begins with one integer ~N~ ~(1 \le N \le 10)~, the number of captchas.
Each captcha will start with two integers ~H, W~ ~(3 \le H, W \le 500)~, the size of the captcha.
The following ~H~ lines will each contain ~W~ characters: either a
- or an
*, which composes the captcha.
It is guaranteed that the captchas are valid.
For the first three cases, ~H, W \le 10~.
For the first six cases, all segments will be of the same length. Note that this means the number of
* in a vertical segment is equal to the number of
* in a horizontal segment.
For each test case, print the digits each captcha corresponds to on the same line. The digits for different test cases should be on separate lines.
1 2 9 7 -*-*-*- *-----* *-----* *-----* -*-*-*- *-----* *-----* *-----* -*-*-*- 9 5 ----- --*-- -*-*- -*-*- ----- -*-*- -*-*- --*-- -----
Note: you do NOT need to pass the sample to pass some of the cases.
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org