Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
70 - ZOJ Monthly, September 2008 - 1001
Triangle War II

Time Limit: 2 Seconds      Memory Limit: 32768 KB

Triangle War II is a new game developed by Cannon Studio.

Different from Triangle War I, Triangle War II is a single-player game. This game is based on a triangle of size N. Below is a triangle of size 4:

We call two dots adjacent if they are connected by a dashed line. As you can see, each dot has at least two adjacent dots (e.g. dot 1 has dot 2, 3 as its adjacent dots), and has at most six adjacent dots (e.g. dot 5 has dot 2, 3, 4, 6, 8, 9 as its adjacent dots). In this game, each dot has two states: pushed and unpushed. Each time, you can choose one of the unpushed dots, push it, change it to pushed state, and change all the state of its adjacent dots (change pushed dots to unpushed state and unpushed dots to pushed state).

Given the initial state of the triangle, you can push as many times as you wish, and your goal is to make the triangle containing as many unpushed dots as possible.

Input

There are multiple test cases. There are two parts for each case. The first part is one line with an integer N (1 <= N <= 6), the size of the triangle. The second part consists with N lines. Each line gives the states for one line of dots, in which '.' represents an unpushed dot and '*' represents a pushed dot. There're no more than 64 test cases in the input data.

Output

For each case, print a number in one line, the maximum number of unpushed dots you can get.

Sample Input

2
.
.*
3
*
*.
**.

Sample Output

2
5

Author: HANG, Hang


Submit    Status