Honey Tour

A little bear Koma likes honey very much. One day, Koma finds a storehouse full of honey. The storehouse has M entrances and exits, is very complicated like a maze. But Koma understands the structure of the storehouse which it is K downwards repetitions of N*M grid, there are some obstacles and the other grids has a honey pot, M entrances are at the top sides of top grid cells and M exits are at the bottom sides of bottom grid cells.

Koma decides to tour in the storehouse following rules.

1.  Koma enters the storehouse through one of the entrances.
2.  Koma can move by one of 4 adjacent directions, cannot go through the obstacles and no grid can be visited more than once.
3.  Koma can eat a honey pot on his position.
4.  Koma can go out through one of the exits.

Koma wants to eat as much honey as possible and he wants to know maximum number of honey pot he can eat when he enters by ith entrance and go out by jth exit and number of that tour.

First line contains an integer T, number of test cases.

For each test case, there are 3 integers N, M, K.

And there are N lines which contains M characters.

‘.’means a grid cell which has honey pot and ‘X’ means a obstracle.

1 <= N <= 5
2 <= M <= 7
2 <= N * M <= 25
1 <= K <= 1000000000

For each test case, first line contains a line “Case #x:”, x is the number of the case.

And then you should output two M * M matrices, first is number of honey pot and second is number of that tour.

ith line of jth number is for the case such that he enters by ith entrance and go out by jth exit.

1
2 2 2
..
.X

Case #1:
4 0
5 0
1 0
1 0

The store house is actually like this.
SS
..
.X
..
.X
TT
S is entrance and T is exit.

And tour is like this.
SS
|.
|X
|.
|X
TT

SS
|-
|X
|.
|X
TT

金策工业综合大学（DPRK）

2016 Multi-University Training Contest 9