8. Number Placement
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a house consisting of several rooms, which can be represented as an $$$n$$$ by $$$n$$$ top-down floor plan (showing both walls and open space in the house).

You are trying to give each open space in the house a certain number. However, you decide that to avoid repetition, all pairs of numbers in the same room must have a GCD of 1.

Given these restrictions, your task is to figure out the minimum possible sum of numbers you can assign to in the open spaces of the house, if you have to assign a number to every open space.

Input

The first line of input contains a single positive integer $$$n$$$ $$$(1 \lt = n \lt = 800)$$$: the width and height of the house.

The next $$$n$$$ lines each contain an $$$n$$$-character string representing the floor plan of the house. An "x" character represents a wall, while a "." character represents open space.

Output

Output a single positive integer: the minimum possible sum of numbers in the open spaces in your house, per the rules outlined above.

Scoring

Full problem: 58 points

Examples
Input
4
xxxx
x..x
x..x
xxxx
Output
11
Input
10
xxxxxxxxxx
x...x....x
x...x....x
x.xxxxxxxx
xxx......x
x.x.xxxxxx
x.x.x....x
xxx.xxx..x
x.....x..x
xxxxxxxxxx
Output
402
Note

In the first example case, you can place the numbers 1, 2, 3, and 5 in the four open spaces.