407971: GYM102953 8 Number Placement

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.

The first line of input contains a single positive integer $$$n$$$ $$$(1 <= n <= 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 a single positive integer: the minimum possible sum of numbers in the open spaces in your house, per the rules outlined above.

Full problem: 58 points

4
xxxx
x..x
x..x
xxxx

11

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

402

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