Some day, Doraemon Hon sends you a new problem as homework. He designs an n*n chessboard and every grid is one of three states. States are “empty”, “star”, and “broken”. You can put the balls on the grids, whose state is “empty” or “star”. The problem is to find the maximum value of the balls you can put on the chessboard. You are easy to solve the problem.
So, Doraemon Hon adds two constraints. One is that the number of the balls on the row i should be equal to the number of the balls on the column i. Another one is that you must put the ball on the “star” grid.
To get the higher grade, you should solve the problem quickly.
If he designs an chessboard with no solutions, please output “impossible”.
The input includes multiple test cases. In each test case, the first line contains one integer n. In the following n lines, every line contains n characters.
1 ≤ n ≤ 40
‘C’ means the “star” grid
‘/’ means the “broken” grid
‘.’ means the “empty” grid
The one line contains one integer, which indicates the maximum value.