{"raw_statement":[{"iden":"problem statement","content":"There is a $N \\times N$ grid, with blocks on some squares.  \nThe grid is described by $N$ strings $S_1,S_2,\\dots,S_N$, as follows.\n\n*   If the $j$\\-th character of $S_i$ is `#`, there is a block on the square at the $i$\\-th row from the top and $j$\\-th column from the left.\n*   If the $j$\\-th character of $S_i$ is `.`, there is not a block on the square at the $i$\\-th row from the top and $j$\\-th column from the left.\n\nTakahashi can do the operation below zero or more times.\n\n*   First, choose an integer $D$ between $1$ and $N$ (inclusive), and a $D \\times D$ subsquare within the grid.\n*   Then, consume $D$ stamina points to destroy all blocks within the subsquare.\n\nFind the minimum number of stamina points needed to destroy all the blocks."},{"iden":"constraints","content":"*   $N$ is an integer.\n*   $1 \\le N \\le 50$\n*   $S_i$ consists of `#` and `.`.\n*   $|S_i|=N$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$"},{"iden":"sample input 1","content":"5\n##...\n.##..\n#.#..\n.....\n....#"},{"iden":"sample output 1","content":"4\n\nBy choosing the subsquares below, Takahashi will consume $4$ stamina points, which is optimal.\n\n*   The $3 \\times 3$ subsquare whose top-left square is at the $1$\\-st row from the top and $1$\\-st column from the left.\n*   The $1 \\times 1$ subsquare whose top-left square is at the $5$\\-th row from the top and $5$\\-th column from the left."},{"iden":"sample input 2","content":"3\n...\n...\n..."},{"iden":"sample output 2","content":"0\n\nThere may be no block on the grid."},{"iden":"sample input 3","content":"21\n.....................\n.....................\n...#.#...............\n....#.............#..\n...#.#...........#.#.\n..................#..\n.....................\n.....................\n.....................\n..........#.....#....\n......#..###.........\n........#####..#.....\n.......#######.......\n.....#..#####........\n.......#######.......\n......#########......\n.......#######..#....\n......#########......\n..#..###########.....\n.........###.........\n.........###........."},{"iden":"sample output 3","content":"19"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}