In Han dynasty, Chinese is divided to three kingdom: Cao Wei (by Cao Cao),
Shu Han (by Liu Bei) and Dong Wu (by Sun Quan). After that, Chinese is merged in one kingdom. In this task, same kingdom is connected in 4 directions: up, down, left and right.
Chinese has R row C column which '.' is sea, 'X' (Greater X) is land. e.g. R=6,
Left image is Chinese land initiation
Middle image describes name of each kingdom
Right image is new Chinese kingdom that cover 2 sea blocks to connect three
Write program to find minimum sea block to cover for connect three kingdom.
First line integer Q (Q <= 15), number of question. Each question
First line integer R C separated with blank space (1 <= R, C <= 50)
Next R line input Chinese map which '.' is sea, 'X' (Greater X) is land.
Guarantee input map has exactly three kingdom.
Q line each line show minimum sea block to cover for connect three kingdom.