In order to celebrate the 8th anniversary of ZOJ, watashi introduces a strange game to other ZJU ACM team members. The board of the game consists of 20X20 grids.
There're some monsters in the grid and 40 buttons along the board. Each row and column is controlled by a single button, while each button can be pushed ONLY ONCE.
If you push a row-controlling button, the health point of all the monsters in the corresponding row will decrease 1.
If you push a column-controlling button, the health point of all the monsters in the corresponding column will decrease 1.
The health point of each monster is 2 initially, and if the monster's health point is 0, we say that the monster has been killed. The goal of the game is to kill as many monsters as possible and you cannot push more than N buttons.
Though Watashi plays the game day and night, he cannot always achieve the perfect goal. Please help him to find the best solution of some specific boards.
Input
The first line of each test case contains the numbers N ( 1 <= N <= 40 ).
Then there're 20 lines, each with 20 characters. The jth character in the ith line correspond to the state in grid (i, j). '.' for the empty grid, '#' for a monster.
The input will contain no more than 10 test cases.
The last test case is followed by one zero.
Output
For each test case output one number, the maximum number of dead monsters.
Sample Input
3
....................
....................
..###...............
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
10
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
0
Sample Output
2
25
