KAMI

Little Bob found an interesting mobile game called KAMI in Google Play recently. In this game, you are given a 16*10 grid, and each cell is one of the 4 different colors.


The only thing you can do in this game is to choose a cell and a color, and then the entire 4-connected component, which contains the cell and has the same color as the cell, will be painted with the chosen color.

Your goal is to make all cells painted with the same color with the least painting steps. Also note that the optimal painting steps will be given, just the same as the original game.

For your convenience, we label the colors with integers 1..4. In the grid, we index the rows with integers 1..16 from top to bottom, and index the columns with integers 1..10 from left to right. Thus the cell in the i-th row and j-th column will be denoted by (i, j).

Once you choose to paint cell (7, 1) with orange color in the above picture, we will obtain:

The first line contains an integer T (T<=5), which means there are T test cases in the input.

For each test case, the first line contains a positive integer n (n<=8), which denotes the optimal painting steps of this case. We ensure this is the least painting times to achieve the goal.

The next 16 lines in each test case describe the initial colors of each cell in the grid. Each line contains a string of length 10, which consists of digits '1'~'4'. For each test case, we ensure that the 4 colors all appear in the initial state.

For each test case, output "Case #x:" (x means the case ID) in a separate line first. Then you should output exactly n lines. Each line contains three integers c, x, y (1<=c<=4, 1<=x<=16, 1<=y<=10), which means you choose to paint cell (x, y) with color c in this step.

If there exists more than one optimal solutions, you can output an arbitrary one.

2
3
4444444444
3332222333
3111111113
3332222313
3111111113
3132222333
3111111113
3332222313
3111111113
3132222333
3111111113
3332222313
3111111113
3132222333
3332222333
4444444444
5
1111213131
1111213131
4444243444
1111213131
4444444434
1111213131
2222222232
1111213131
1111213131
1111213131
1111213131
1111213131
1111213131
1111213131
1111213131
1111213131

Case #1:
2 14 2
3 15 7
4 12 8
Case #2:
4 4 5
4 16 9
2 5 10
1 7 10
3 16 10

2014 ACM/ICPC Asia Regional Anshan Online