Harmless Rooks

Statement

Goal

The rook is a chess piece that can move along its current line (horizontally) or column (vertically) through any number of free (unoccupied) squares.

In this problem, we consider an N × N generalized chess board where the squares are either free (. in the input) or already occupied (X in the input) and hence cannot be crossed by the rooks.

Compute the maximum number of rooks that can be placed on free squares in such a way that no two rooks threaten each other (hence two rooks on the same line/column must be separated by at least one occupied square).

Input

Line 1: An integer N, the size of the square board.
Next N lines: A string of length N describing a line of the board, . indicates a free square and X an occupied one.

Output

A single integer corresponding to the maximum number of rooks that can be placed on free squares without directly threatening each other.

Constraints

1 ≤ N ≤ 99

Example

Input

5
XX..X
....X
XX.X.
X....
.....

Output

Tags

Optimization, chess

Difficulty

Hard

Test cases

Size 5 Test

Input

5 XX..X ....X XX.X. X.... .....

Output

Validator 1 Validator

Input

5 .X.X. ..X.. ..X.X ....X X..X.

Output

Size 8 Test

Input

8 ........ ........ ..X...X. X.....X. .XX.X... X...X... ........ ..X....X

Output

Validator 2 Validator

Input

8 .X...... ...X.... ........ ........ ...X.... X..X.X.. ......X. .....X..

Output

Size 16 Test

Input

16 .X......XXX..... .X.............X .....X.......... X..X.......X.X.. ..XX..X..X.XXX.X X............... ...X...X..X.X.X. .X.X..........XX ...XX.XX....XX.. ....X...X.....X. .X......X....X.. .X.X...X.X..XX.. .........X...... .X..X.X........X .X..X.X....X...X ..X.............

Output

Validator 3 Validator

Input

16 ..........XX.X.. X.X....X........ ..........X.XX.. X....XX.X..X...X X....XXXX...XX.. ........X...X... X......X.X.XX... .....X........X. ..XX.XX....X.... X.....X...X.X... .XX....X........ XXX.....XXXX.XX. ............X... ..X..X...X.X..X. .........XX..... .....X.........X

Output

Size 30 Test

Input

30 XXX.X.X.....X..X......X..X..X. X........XXX........XX...X.... .X..XXXXXX.......X...X......X. ....X.....X.....X.X.X...X.X... .XXXX..X......XXX.X...X.X..... X..XXX...XX..X......X..X.....X ....XX...XX..X..X....X......X. .......X..X...X............X.X X...X.X...X.......XX.X..X...X. ...XX........X.X..X.XX....X... .X.....X...X....X...X..X...... .X....X.....X.X..X..X.X......X ...X......XX.XXX..X.XX.XXX.... X.....XX...X.X..............X. ...X......X...X...X...X..X.... .XXX.X.....X...............X.X .XXX................X.X.XX.... ...X......XXX..X....X...X..X.X ..XX...X..............X..X.XXX .X..X......X.........X.X.XXXX. X..X......X.....X.....XX....XX ..X.X.XX.........X.X.XX..XX... ..XX...X....................XX ..X...XX........X.......X.X... ...X..X..X.X....X..XX...X..X.. ....X..X.....X............X.X. .XX.XX...X.X..X........X...... X........XX..X..X....X....XX.. X.X.X.....X..XX......X....X... ...X.......X.X..X...........X.

Output

165

Validator 4 Validator

Input

30 X.X....X..X.........X..X..X..X ......X.......X....X....X..... .X.XX..XX..X...X.XX.X..X...... .X..XX.....X.XX.....X......X.. ...X....XX......XX......X..... ..X.X........X.X..X...X....... .X......X.....X..X..X......... ...X..................X..XX... X.XX.X.......XX...XX....X...XX ..XX....XX.....X..X....XX...X. ....X.X.X.X..X.............X.. ....XX.X.........X......X..X.. X....X.....X..XX..XX....X...X. ..........X.X..X...XX..XXX..X. ..X...X.XX...X....XX...XX..X.. .X...X.....X.X.X.X.....X.X.... ..X.X................X.X...... ........XXX........X....X.X.X. X....X..........X..X..X....... .X..X..XX......X.............. X..XXXX..............X.X..X... X....X.....X.................. ....................X.....X..X ......X................X..X... .....XXXX......X..XXX..X.X.... .....XXX.X...X....XX.......... .....X.....X.....XXXX.X.X....X ...X.X.........X..........X..X ...X......X..XX....X.......... ....X...........X....XXX.X....

Output

150

Size 50 Test

Input

50 ..X..XX.X.....X...XX.X............X.XXXXX..X.X.XX. ...X..X......X..XX.X.X.X.X.....X.........X...X.... ....X.X.....X.XXX.......X..X...XXX.......X.....X.. .X.....X....X..X....XX...X.XX...X........XX....... X.....XX..X......XX...X.XX..XX..XX.......XXX.....X ...X.X...XXX.X....X...X..X.X.X.......X.X...XXXX.XX X..X..............X...X...X...X.XX.X..XXX.X....... ....X...XX......X..X....X..X.......XX..X..XX.X.... ..XX..X........X.XX......X....X.XXXX.....X........ X..X....X...X.XX..X........XXX.X.......XX...X.X.X. .........XX.X...X..X.XX....X.X.XXX.X.......X..X... X......X..XX..X.X..X...X.XXX....X.X.X.XX.X..X.X..X XXX......XX..X...X...X.....XXX.X...XXX..........X. .X.X........X.X.......X...X.X..XXX...X..X....X..X. .....X.X.XX.........XX......XXXX....X....X...X.X.. X.XX........X.XX..X...X..XX..XX.X.X........X...... ...X....XX..XX.X..X.X...X.X.......X........XXX..X. .....X..XXX....X.....XX..X.....XX.X.XXX.X.X...XX.. X...........X.X..X....X.....X......X.........X.... X.X.XX....XXX.X.X.......XX.....XXX.........X...... .XXX..X..............X.XXXX...X.............X...XX ......X......X..X.XXX....XX..X....XX..X..X...X.X.. .....X..X.........X.X...X.X..XXX..X.X.X..X.X.....X .X.X.X...X.X...X.....X..XX.XX..........XX..XX..... XX.......X.XX..X..X.....X...X....X...XXX..X.XXX..X ......XX..XX....X.XX..X..X..X.....X..X.X....XX.... XX.XX...X..X........XX.X.....XX.X.....X......X...X X..X......X.....X..X..X.....X.X....X......X.X..... XX..XX.....XX..XX..X.X...X......X......X..X..X..X. XXX....XX...X.XX..X..X..XX.....X..X.X..X....XXX.X. .X.....XX..X.........XX.XX....X........XXX.X...XX. XX........X..XX.....X.....X.X..XXXX.....X.......XX .X....X......X.X.X..XX..X..X.X......XXX....X.X...X ......X....XX...........X...X.........X......X.X.. X..................X.......X.......XX...XX...X.X.X ....XXX.X..XX....X..........X...XX.X..........X... XX.X.X..XX...........X......X...X.....X.......XX.. .XXX..XX...X..X....XX....XXXX.X.X.X.X.X.XXXXX...X. .XX....X....XX..X.......X..XXX..XX..X.XXXXX.X...X. ....XX....XX.X......X.X...X.XX....XX..XXX...X.XX.X X..XXX....X..........X.XXX.XX....X.X....X......... .X...X...XX..X.........X..X.X..XX..X.X......X.X.X. ...X.X....X..X.XX...X................X.XX.X......X X.X.XXXX....X.X.X..X......XXXXX....XX............. X..XXXX.X........X.XXXX.X....X...X..XX.XX..XX..... ...X..XX.X......X.X..XX..X.X.....X.X..X..XX....... .X.X.....X......XX..XX..X.....XX.X...X..X.X....... X.......X...X...X.......XX......X....X..XXX....X.. ....XXX..X.X....X..X..X...X.X.X.....X.X..X.X..X..X ......X....XX.X......XX...X..XX...XX.X..X....X....

Output

484

Validator 5 Validator

Input

50 ...X.X..X.......XX.X.XX.....X..........X.XXX.XX.XX .......X...XX..X.X.....X.X..X..X..............X... ....X...X.XX..XXX..X...XXX...X...X........X.X...X. .XXX...X..XX.X...XXX.X....XXXX..X...X....XX.XXX... ..X..X.....XX.....X....X.X.XX..X..........X.X..XX. ....X.XX.....XX.X.XXXX.XXX........X......X.X.X.X.. XX.........X....X......X.X.....X..X.......X....XX. .X....X......X..X.X..XX.XX...X.........XXX....X... .........X.X......XX.....X.X.......X........XX..X. X..X.X......XXX....XX.X.X............XX..XXX....X. X....XX.XXX.....XX....X.....X...X...X.X.X..X..X... XX.X...X..XX.....X.X....X.XX...............X...... .....X.........X..X..X.....XX..X..XX.....X...X.X.X .X...X....X.X......X...X.X........XXX......X.XXXXX ....X....X.......XX.........X..XX.X.XX..X.X.....X. X.....X......X.XXX..XX........XXX...XX.X....X..... ...XX.....X....XXXX.X..X..XX..XX.......X..XX...X.. ....X.X.X...X..X.X....X.XX....X...X.XX.X.X.X..XX.. X.XX.X...XX..X..X..X...X.X..X........X.XX......XX. X.....X.X..........X..XX............X..X.X...X.... XXX..X.....................X......X...X.XX........ ..XXX.XXX.X..XXX.........X....X..X.X.....X..XXX... ............X.X.X..........X...X....X.........XX.. X..XXXXXXX.XX.....XX.X.X..XXX..X.....X..XXX....X.X .X.XXX....X....XX.....X.X.......X.X..X......XXXX.. XX..........X...............XX...X..X.XX..X....... X.X..XX...X.X...X...X...X.........XX..X...X....... ..X.XX.X..X..X...X..X..X...X..X.X..X...X.X..X..... ....X...XX...XX.X.......X....X....X..X.X.XX.X..... X.X.XX.XXX......X..XXXXX..............X.X.X..X...X ...X..........XX..X..XX...X..XXX...X......X.X....X .X.XX.X..XX....X......X.......X..XXX.XXX..X....... ..X.X..XX.X.XX.....XX..X.X.XX....X...XXX....X.XX.. ..XX.X..XXX.XX...X.X..X.XX...X.X..X......XX.X.XX.. .XX.XXX.X...XX.XX...X..X.X......X.....X...X.....X. ...XX.XX.X.X..X...X...X...X....X....X..X.......X.. .....X......XX..X..X.XXX.............XXX.....XX.X. .......XX.X.X.XX.X.XXX.XX..X..X.X.XXX......X.....X X.XX.XX.........X.X....X.......X.X..X....XX..X.X.. ..XX....X.X.X...X..X.X.X......X..X...X..X.X..X.X.. ....X.XX......X.XXX..XX..X.......XXX...XXX...X.XXX XX.X..X...XXX.X......X....X..XX.X.....X.XX.......X X...XX.....XX.X...X..XX...X.X.X..X...X....X....... X......X.X..X.X...X...XXX.XX.........XXX.XX.....X. .....X.X.X.X.XX.XX..XX..X....XX....X......X..XX... ..XX..X....X.XX.....X...X.X..X.....X....X..X..X..X ..X.....X....XX.X.....X.X.X.........X....X.X.XX... ...X.....X..X......X..X.X.X.X.X......X.X.X.XX...X. X.X.....X.X.......XX.XX..X...XX.......X.XX..XXXX.X ...XXX.X.....X...X...XXXX....XX.XXX....XXXX.......

Output

489

Size 99 Test

Input

99 ..XX..XX....X...XXX....X....XX..X....XX.......XX...X.XX......XX...........X...X.....X..X..X....X... ....XX...X.X.X......XXX.X.X...X.X...XX..X..X............X...X...X..XXX..XXXXX.X..X.X...XX.X....XX.. .....XX..X....XX.X....X......X...X...X.XX...X.X.X...X....X.........X...X..X....XX....X........XX..X X.X..X..X......X.X.X...X....X..X........XX.X........X....X..........X.....XX.X.........X........X.. .X...X....XXX.......XX.XX.....XX......X.X......................X.......X.XXXX.X...X......X.X..X.... ..X..X..X........X.XXXX....XXX..X..........X..X..X.XX..XX..X.....X...X.....X....X.....X....X.X.X... ..X..X.........XX.X...X.XX.X.X.X..XXXX...X.....X...X......X...X.X.XX...X....XX...........XX...X.... ...X...X.XX.XX.XX.X....X.XXXX.X...X.XXX...XX...X.X.X..X..X.XX....X..X.X...X......XXX...XXX...X.X.X. .X..X....X............XX...........XX...XX...XXXXX.XX..X...X......X..X.X.......X..X...X.XX.....X... X.....X..XXX..X.XX.XXX.X.X.X....X.....X.X...XX.XXXX........X....X...X...X..X.....X.X...X.....X..... .......X.......XX..X.X...X.........XX.....XXXX.....X....XX........XX..XXX.....XX.X.XXXXX........... ..XX.XX.......X..XX.X..X....XX..X...X...X......X.X.X.......X...XXX..XXXX.XX.X.XX......X.X.X..X..XX. ....XX...X.X.X.X..XXX....X..X..X.X.X.XX...X.XX.X.XX.XX.....X...XX..............X.X..X.X..X.....X.XX X..X.X...X...X..XXX..XX..XXXX.XXXXX..X.XX.....X........X.XX.........X........XXXXX..XX...X...X..... XX...XX.XX......X..........X.....X.X.X..X...X.....X...X.....X....X......XX..XX....X..X.XX...XX.XXX. X..X.X....XXXX.XX..X..X....X...X...XX.X..XX....X................X..X.X.X.XX....X...XX...XX.XXX.X... X.X...X.....X..XXX.....X...X.X..X...XX.XXX..X..XX......X...XX....XXX....X..X..XXX...X.......XX..X.. ..XX..X..X....XX....X.X..X..X.X.......X..XX...X..XXX..X..X....X........XX.....XX....X..........X.X. ........X..XX.....X....X..X.X.X..X.XX...X..X...X..XX....X..X..X.........X......XX..X.X...X....X.X.. X..X...X.........XXX..X..X....XXXX.....XXX...XXX..X......XXXXX.XX..X..X....XX..X.....X..XX....X.... ........X.......X.X..........X..X...XX...X.X...X........X.XX.X..XX.X.XX..X...X...X........X......X. X...XXX..X...X..X......XX.X.X..X........X...X.XXX..X....X.....X....XXXXX....X.......X....XXX......X ..X..XX..XXXX..X.X.XX....X.X....X.X.XX...X........X..X...X.X.........XX................X.XX..X..... ..X...X....X.XX....X...XXX...X..XX......X...X.XX..XXX........XX.XX..X.......X..X...X....X..XX..X.X. XX.XX....X.......X.X..X.......X....X..X..XXX.X.X.XX.....X..XXX..X.XX..XX.XX..X..X..XX.........X...X ...X.XX..X.....X.....X.X.........XX..X..X.X.X.XX.....XXX..X.XXX.XXX...X...X.X.X..X.X..XX.X.....X... ..XX..X....X.X.X..X...XXX...XXX...XXX.X.XX..X.X..X......X...X..X.......X......XXXXX....X..XXX.X.... .X...X.XXX..X...XX..............X..X...X......X.X.X..X..X.X....XXXX.......X.X...XX.X.XX..X..X....X. ....X.....X...X..X....X.XX.X..XX...X.X...X...X.X.X...X.X......XX..X..X........X.....XX..X.XX...X... .....XX.......X..XX.X...X.X.X.XXX.XX.......X..X..X...XXX..X.......X..X....X..XX......X....X.X.X...X .......X...XX.......X.X....X.X...X..XX...X..XX.X.X....XX...XX.......X.X...X........X.X.......X...XX .XX.............X...XX.X..XX...X.X.X.X...X....X.X.X..X.X...XX...XX.X.......X...X.....X..X.X...X.... ....XX.X.XX.X....XX.X...XXXXX..........X.X.X....X.......XX......X...XXX....X.......X......X.X...X.. ......X....X..X........X..XXX..XX.......X.X..XXX...X........XX.....XX.X...X..X....X..X....XX....... ...X.X.....X....X.....X.X...............X.X.....XX..X...XX......X....X....X.......XX....XX...XX.XXX ...XX.X....X......X...X....X...X..XX.X..X..X.X.X........X...X.....X.X.XX...X......X...X.X.X......X. .X...X.......X..X.X..XX..XXX.X...X...X.XX...XX.X.X...X...X...XX.XX..X..X...X..X.X.X.X....XX.X.X...X .....X......XXXX....X.XX.XX.XX..XX.....X..X..X..X...X.XX...XX...X..X.X..X..XXXXX....X.......X..X... ...X..X..X....XXX..X...XX...X...XX.X..X.X..X.X.....X..........X.....X....XX.X.X............XX...X.X ......XXX.X.X.X.......X.X..X....X.X...X..X.X.X...X.XXX....X.........X.X.......XX....X........XX.X.. .XX.....X......X...X..X.........XX...X......X.X..XX...XXX..X.X..X....X..X........X...XXX......X..X. X...X..XX..X.X.......XX.XXXXX..X...X.X..X....X.....X.X...XX.XX..X...........XXX.....X...X...X.XX.XX ...X..X...X.X....XXX........X.XX.X.X.....XX.XXX.........X....X......X...XX...X..X....X.X.X...XX.... ...X....X......X......X............X......XX....X...XX.X..X..X............X..X.X.........XX...X..XX X..XX..XX.X...XX..XX.XX..X....X..X.......XXX....X.X.....X.....X..X.X......XX...X..XX....X..X.XX.XX. .X.X.....X..X.X...X...XXXX...X.XX....XX..XXX.X...X..X.X.XX...X..XX..X...X...X.X....X.....X.X.XX.... ..X...X..X.X..X.X.XXXX.X..X.....XX.X.......XX..XX......X..XX......X......X..X...X.XX....XX..X.X..X. ....X.XX..X.X.X..XX.X....X..X.X.X...X..XX.X..X.XXX..X........XX..........X..XXXX....X....XX....XX.. ....X....X.X......X.X.X..X...X.X.X...XX....X...X.X...X....X...X.......X.XX.....XX........X....X...X ...X.X.........X..X.X.....XX.X..X...........X..XX.X...XX.XX....XX.XX.....XXXXXX...X..XX...X.XX.XX.. X.X.X.X.......X..X.XXX...X.........X.X..X....X...X..XX.....X.XX......X.X.X...............X..XX..... X..........X..X..XX...X.....X...XX....XX.........X..X.X.X..X..X....X..X...XX.X......X.X.....X.X.X.X XX......X........XX.X......X........X..XX...X.X...X.....XX....X....X...XX.XXX...X...X..X..X....X... .X........X..XXXX..X....X...X....XX..........X...X.....XX..X....X.X....X.X...X..X...X....XXXX..XX.. XXX.X.XXX....X...X...X...XX................XX..X.X..X...XX.X...XX......X.XXX.....X....X.X.XX.....X. .X......X.....X...X.X.X...X..XXX.....X..X....XX..X..X...X.X.X..XX.X....XX..X..XX.XX.X......XX.XX..X XX.X....X..X...X.......XX....X.........X.XX..X.X..X.X...X......XX.X.X.XX...X....X..........X.XX.X.X ..X.........XXXX....X.....X..X...XX.X.X.....XX..X......X.....X..XX........X.XX.......X...X...X..... .XX..X.X.X...X..XX..X.X.XXXX..XX...X.X.....X..X..X.X.X...XXX.X..X.X...X..XX.XXX.X.X...XXX.X.X...XX. XX...X..X.......XXX....X.XXX...XX.....X.........XX....XXXXXX.X......X....X..XX..X..X.X...XXX....XX. .X.....X......X....X..X..X.XX...........XXXXX......X........XXXXX...X..XX..XXX..X....XXXX...X...... XX......XX.XX.X..XXX..XXX.X..X....XXX...X.X..X....X..X........X....X.X..X....X.X..XXXX..X....X.XXXX X.XXX..X..XX......XX.....X..X.X..XX..X...XX......XX.X........X......X..X.X...X.X.X....X...X....X..X ..XX.XX.X.......X..X..X...X.XX..X..X.XXX......X....X..X.....XX.XX....X.X..XX...X......XX..XXX.X..X. XX.....XX.XXX.........X.X..X.XX.X.X.......XX.....XXX.....XXXX.X..X.........X........XX....XX...X.X. .X.......X...X.....X.XX.X.....X.....X.XX.....X.X...XX..X..X.X....XXX.....X.X.X.........X..X.X..X... ......XXX.....X..X.X....XXXX....XX..X.....XX..........X..X..X..X.X........X.XX..X..XX.X.XX.XXXX.X.X .X...X.......X..X....X.......XX.XX..X.X..X.X.X.XX.X....X....XXX....XX...X.X.X.X....X..X.XXX.......X X..X.X........X..X.XXX......X..XX...XX..X.X.....X.X.X...X...X........X..XX..XXX.......XXX........X. .X..XX..XX.XX..X.X.X......XX..X.X......XXX...XX.XX..X..X.......X.XX......XX...X....X.XX....X.XX..X. ....X.X..X.X..X.XX.X.......X.......XX.X.XXX........X..X..X..X.X.....X.......X......XX...X.XX.XXX.X. ...X......XX.XX...X.X.......XX.....X.X.......X.......X...X.X............X.XX..XXXX.XX...X.......X.X X...X....X..X...X...XX.X.XX..X..XXX....XX.X..X...X.X.X.X....XX...X....X....X....X..X.X.......X....X XX.X....X.X...X..X.XXX......XX..XX..........X....X.X......X.X.X..X..XXX.....X.XX.X.....X..XX..X...X ...XX...........XX....X...XXX.........X.........XX...X.XX..X...X.XXX..XX.X.........X...X...XX..X.XX ..X.X..X........X.X.......X.XX........XX....X.X.......XXX.......XXXXX.XXX.......XX..X....XXX.X.X..X ...X.X........X.X..X.XX.X..........X..X..X..X................XXX....X..X......XXX...X.XX...XX..XXX. .X..X.X....X..XX.....X..XXX.X.X....X.X........X.X...XX..X..XX...XX.....X.X....X...........X..X...XX ...X...X.X.........X...X.XXXXX...XX.X..XXX..X.XXX.X..X..XX......X.X.X..X....X....X.XX......X..X.... .X...XXX..X.....XX.XXX.X.........X..XX..X....X....X..........X............X.X......X...X.......X... .XX..X..XX......X....X...X...X...XXX..X...XX....X...X..X.....XX.....X...X..X.........X...X..X.XX... ..X...XXX....XXX....X...X..X........X.X.X...X.X...X.XX.......X.X..XX..X......X...X..X..XX..X....... X.X.XX.......X.X.......X.XX.....X......X......XXXX...XXX..X.X...X..X.X.XX......XX.....X....X..X.... ...X...XX.XX.X...XX..XX.X.........X.XX..X.X.X..XX..XXX.X......XX..X...X..X..XX....X.X.X..XX....XXXX ......X...X...X..XX......XXX.XX.X..........XX.X.X..XX...X...X......X.X.X....X.XXX...XX..X....X..... .....XX..X.....X........X...X..X..XX..X.X....X.........X.........X.....X.X...XXX.X.X.X...XXX.X..... .X..XX.X.X..X....X...........X.XXX.XX...X.X...XXXXX.XX...X......X.......X..X.X.X....X.X..X.X.X..XX. X.X..X......XX...XX...X.....X.X...X..X.....X..X..........X..X...XXX.XX.X.X....X....XXX...........X. ...X.XXX.X..X.X......X..X.X...X.XX.XXX.XX.......X..XXX..XX.........XX..XXX....XX...XX.......X...XX. X......X..XX...X.X.....X..X...........X..X....X....X.XXXX..XX..X.X.X..XX....XXX......X........X.... ......X.....X.XXX..X..XX..XX.........XX...X......XX...X......XX.X....X.XX....XXXX....X..XX.X..X.... X.XX..XX..XXX..............X....X..X....X....X.......XX.XXX........X.X...XXX..X.XX..X.............. ......X.......XXXX.....X..XX.X.X.XX.X.........X...X.XX...XX.....X....X....XX..X..XX.X......XXX...X. X........XXX......X...XX......XXX...X.........X.XX.X......X..X.X..X....XX.X.X.X.....X.........XXX.. ........XX..X....X.....X.X...X......X..X....X.......X.XX.X.X......X....X....X.X...XX.X.XXX.XX.X..X. ....XX......XX..XX.......XXX.....X...XXX......X..X...X..X.....XX.X.XX..........X.X...X.....X....... X..X..XX..X.X..X..XXX...XX.XX..X..X.XX.............XXX..X..X........X.....X..X.X.X.X..X...X...XX... ...X..X..X..X......X..X..X.X.XX..X.X..X.X.XX...X...X......X.X....X...X...X....X........X.X.XX.X.XXX ....X..XX....X..X.XX..X....XX.......X.XXXX...................XX..XX..X.X.X......X..X....X..X.......

Output

1911

Validator 6 Validator

Input

99 XX.....X............XX..XX....X.....X........X..X.X..X.XX.X..X....X...X...XX.X........X........XX.X ...X..........X.X.XX.XX....XXX...X.X....XX..X.X.....X..X....XXXX...X..X........XX.....X....XXX..... ........XX..X.XXX.XX...XX..X.....XX......X.X...XX.X....X....XX....XXX....X.X.X..X...X.X.....X...X.. ..X...XX.X........X......XX.....X..XX.......X.....XXX....X.......X.X...........X.....X....X.X..X..X ................X......X...X.X.X..X.X..X...X......X.....X......X.XX...X.XX....X....X.X.XXX.X....... XXXXX..XXXX..........X.X...XX..X..XX.......X..................X..X....X...X.X.......X..XXX.X....... .X......X...XXX..........XX.X..X...XX.X...XX...X..X.XX......XX..XX..XXX.XX..X......XX....X..X..X... ....X....XX.........X...XX.......X.XX......X.X.X.XXXXXX...........X........X.X..X...XXXX.......XX.. ..X....XXX....XXXXXXX.X.XX......X.....X....X........XXX...X...X.X..X....X....X.......XX..XX...X..X. .X.X..X.X..XX.X.........X......................XX........X..............XX....XX.X.X.X.X.XXX....X.X XX.......XXX.XXX...XXXX...............X..XX............XX.X...X....X.X....X.X..X...X..X...XX.X..X.. ........X.X...X.XX.X...X...X.X..XX.....X.X...X.....X....X...X..X.XX.XXXX..XXX..X...X.X..X.......XXX ..........XX.....X.X...X..XX..XX.X...XX..XX..X.......X...XXX.....X.X.X...XX..XX.X.XX..X..X...X..X.. XXXXX.....X......X.X.......X.........XX..X..XX......XX..X..X.X.XX....X...X.......XX.X.....X....X... .X....XXXXX....X.X...X....X.XXX....X.....X.X.....X....XX..XX.X...X.X..X.......XX.....X....XXX..X..X .X..X....X..X......XX..X...X...X.XXX..X.XXXX........X......XX..X..X.X.XX....X.....XXX..X....X.....X ..X..X.X......XXXX......X...X.X......XX......XX.X........X.X.XX..XX.X....X...XX..XX.X.....X.X...... X..XX..X..X......X....X..XXX.....X.XX.X...XXX............X...X..X....X....XX........XXX....X...XX.. X..XX..X.XX...XX.....X...X...XX.....X.XX............X.....X.X..XX..X...X..XXX..X.X...X....XX..X..XX XXX.XX.X.XXXXX......XX..X.....XX......X..XXX.....X..X......X.X..X..X....XXXX......X....X.....X..XXX ...X...X.X.....X.........X..X..X...X...X..X.....X..XX.....X..X.X.......XX.......X....X...XXX.....XX .XX...X..X...XX..X.....XX..XXX....XXX.......X..........X..XX.X....XX.XXX.XXXX..X..X..X.X.XX....X.X. X.......X.X.X.X.X........XXX.X....X.XX.X.....XX.X...X...X...X......X..X....X....X...X.......X..X.X. X..XX.X.X..X.............X...X..X.XX..XX..X..X..X.X.XX.X..X...XXXX.X..X.XX...X........X..X...X.X... X...X...X.X.XX.X...XX....X......XX........X........X.X..XX...X.XX..XXXX....X....XX.........X....... ........X..X...X.........X.X.......X..X.X.....X..XXX.....X.X....X.......XX.......X......X..X...XXXX XX.XXXX.XX.....X.XXXX....XX.X....XX........XX..X.XX....X.X.X....X..X.X.X..X....X.....XX...X......XX ...XX....X.X.X..X.X...X...X.X..X..X...X.....XXX.XX.X...X..X...XX......X.....X..X.....XX..XXX.X..X.. ..X..X..X....X.XX...........XX....X.....XX....XX.....X....XX.X..X.......XX....X.....X.X..XXX..X..X. .....X.........XXX...X.X........XXX.XXXX....X...X.X..X....X..XXXXX...X.....X..X.X...X.XX...X..XX... .X....X.X..X....X..X..XX..X.X..XX...XX.X..........X.XX.....XX...............X...X...X..X...X....... ...X..X......X.....X.........X.X........X..X..............X........XX........X.....X........XX...X. ..X..XXX..XX.X...XX...XX...X.XX.X.X.X.X.................X.XX..X..X.X..X...XX.X..XX.....X.X.X....X.. X.XX.....XX......X..X..X...X....X....X...XX..X...X..XX...X.XX...XXX....X.....XXXX.....XXXXX.......X .........X.......X.X...X........XX..X.....XX.....X.X...X.......X.X..X..X...XX...X..XX..X.XX.....X.. X..X.......X....X..X.XX....X.X...X..X.....X.....X.........X.X..X.....X.....X.X..X.X.XX..XX..XX...XX .X...X.X...X..X.XX.X....XX........XX....X.X.X...X........X....X.X....X....XX..X.X.X....X.X.X....... .........................X............XXXX.X.XX..XX...XXXX.......X....XXX...XXXX..X.....XX......... X...XX.XX....X.X...X.......X.XX.....XX...XX....X..XXX..X.X...X...X.X...X.XXX...X...XXXX.....X...... ...................X.......XX....XX..XXXXXX....X.X..X.X..X.X...X..X....X.XXX.X...XX....X...XX...... XX.....X.XXX.....X.....XXX..X.X.X.....X.X....XXX.XX..X.........X....X.....X.XXXX.XX...........X.... ...X.X.....X....X.XX...X..X.XXX.X........X...XX...X.X...XXX.X....X....X.X.X....X.....XXX..X.XX.X... .X...........X.XXX..X.....XXX..XX.X....X....X.X....X....X.....XXX.....XX.X..X.X...X...........X.... ..X.....X.X.XX.X...X...X.....X.......X....X.XXXXX..X...X....XXX..X....X........XX..X.X...X.X.....XX XXX......XX.........XX.......X..X.X....X...X.X...X..X.X...X......X...X......X........X.XX.XX.X..... X.X..XX.....X.......X.X.XX....X..X.X.X.X...XX.XXXX.X..XX..XX....X.X...XXX......X.......X..XX..X.... .X..X.XX.X.X.X...X...XXXX..X..X..X..............X.XX..X...X....X.......X..X.X.........X......X..XX. XX.X....X.XX..X.XX.XX.XX..........X................XX.....X.X.X..X....X....X..XXX.XXX..X....XXXXX.. ...X....XXX........X.X.X...XX...X.X....XX....X.X..X...X...XXX.X.........X..X....X.X..XX.XX.XX..X... X.XXX.........X.X...XXXX.......X...X..X...X.X...............X.XX....X....X......XX..XX....XX..X.XX. .....X.X.X..X..X.X...X.....XX...X...................XX.....X.....X.XX..X.X........XX.X..XXX..X....X XX........X.....XX..X...X.....XXXX.....X.X...X.........X....X.XXX.X....XX..X....XX..XX.....XXXX.XX. XX......X..XX.X........X.X..XX.........X...X....XX.......X.X...X..XX......XXX..X........X......XXX. .XX..X...X....XX...X..XX.X..XX..XX.......X.X......X.X...X.X.......X.X..X.XXX..X...XXX...X.........X XX...X...X.X....X....X..X.....X.......X.X...X..X.XXX.XX.X......XXX..X....X....X..XX.......X.XXX.XXX ...X..X.....XXX..........X.....X...X...X.....XX..X.X.XXX.........X.X.XXXXX..X.X..X..X..X........X.. .X....XX..X....X...X...X.XX...X..............XX.XX..XX..X.X....XX.......X....XXXX......X......XX... .X....X.........XX.X...XXX.XX...X..XX.X..X.....X..............X..X...X..XXX...X..........X...XX.... ..............X..XX....X.XX.X...X.......X.....XX..X..X..........X....X....X...XXX..X..X....X.X.X..X .XX.X.......XXX.....XXX.....X.XX......X......X....XXX.XXX.X..X...X.......X.....XXX.......X..X...X.X XXXX.....X..X...XX..X.X..X.X.X.....XX....XX.......X..........X..X..X..X...XXX..X....XX..XX........X .XX.....X....XX..XX.X...X..XX.X....X....X.XX......X.......X..X......XX..........X...X.........X.X.. .XX..X.XXXXX.X..X.XXX.X.X..X..X.....XX...X..X...X..X.......XX..X..X.XX.....X...........X.....XXX... ..X......X...X....X.X.......XX..XXXX.X.....XX......XXX.X..XX.XXXXX..X.XXX..XX..X..XX...X....X...X.X ..X..............XXX..X.......XX...X.XX.XX....X.XX........XXXXX..X.......X..X.X...X....X...X.X..... X.X.XXX....X.X.......X....XXX...X..XX.X....X........X..XX.........X......XX..X......XXX.XX.X....... .......X..XX.XX.X.......X.X......XX...XX.X.....X...X...X.X...X........X...XX...X..X.X.......XX..X.X XXX........X.......X..X..X....X.....................X...X.X...XX......X.X.X.....XXXX......XX...XX.. XXX.X..XXX......X.XX...XX.XXX..X.....X...X..X...X..X..X...X..........X....X...XX.X...X.......X.X.X. X.X....X..X..XX....X....X.X.....X....X..X....X...X.X....X.....X.X.XXX.X..XXXXX...X..X..X...X..X.... .X..X......X...X...X.XX....X..X....X...XXXX....X...X.X..XXX......XX.........X..XX..XX.X......X.X..X ..X.....X.X...X....XX................X..X..X...XXXX..X....X.XX.X..X.X.XX...X.....XX.X.X.........X.. XX.............X...X..X....X.X....X.X...X.....X.....X.X..X.XX.X..X...X.......XX......XX..X.XX.X.X.X ............XX......X........XXXX......X..........XXXX...X.X..XX.......X.......XXX..X.XX.......X.X. X.X.....XX..XX..XX..X.X...XX...........X......................X........X........X.X.X.......X...X.X ...X.X.X....XXX..X...XX.........X..X..X....X.XX..X.X.X.X..X.X..X..XX..X.X.XX.X..X.XX............X.. .....X.X.XXXX...XXXX..XX....XX...X.X...X..X...XX........XXX..............XX........X.X.......X..... .XX..X..X.......X...X..XX.XX.......X..X.....XXX.....X.X.XX...X....X...XX...........X..............X X.X.XX...........X............X.XXX....X...X.............X.X.....X.XX...X......XX..X.X.X..........X ...X.XXX.X..X......X.....X.X.XX..X.X.X.X....XX..X.X......XXXXX..X.X.........X...XX..........X....X. .X.....XX..X....X................XX.X...X.X.X.....XX..X.XX..X..XX...X..X.....X..X.....XX.XX.......X ...XX.X.XXX..XX......X..X.X..X...X.X..X..XX....XXX.X..XX..........XX.X......................X...... X.X...X.....X.X.X..XXX.X..X...XXXX....X.....X.XX....X..X........X.....................XX.....X..XX. XX...X..........XX.X....X.......X..X....X.X.......XXX............X.XXX..X.XXXXX....X...X...X....XXX X.....X..X.X....X...X...X.X..X......XXX.X..X..XX.X...XXX...XXX...XX...X.X...X..X.X.X..XX........... .X...XX.........XX...X....XX.X..X..X.X..X..X..X..X..X.X...X.X...X...X.....X.X....X.......X....XX... .X...X....X..X.X..XX..X....X.X.......X.X..X.X......X.X.X.X.....X...X...X.XXX.XX.X.X..X......X.X.XX. XX..X.XX...X.X..XX.X.....XX...XXX.X....X.XX...XXX........XX..X..XX....X.X..X....XX.X..X....X...XXX. ..XX............XX....XXX....XXX..X..XX....X...XX...X...X......XXX...X.X............X....X.X..X.XX. ...........X....XX........X.XX...X.........X...X...X.......X...X....X..X...X.XX..X......X....X...X. .XX...XX...X.....X.X.X.X..X...X.X...X..XXX.X......XX.X....X..X....X...X.X........X....X.X.XXX.X.... ..X.XX...X..X...X...X....X.............X.X..XX..XX.X.XX.X.......X..XX.XX...X..X.XX..X..X...XX...... X....XX.X...X....X......X......X.....X.X.X.XX........XX.X...X....X.XX.....XXX.XX...X.X....X....X... ..........X.......XX....XX.....X...X.XXX....X..X..X....X.X......X...XXX..X..X.X.X.XX....X..X..X...X .X..XX..X............X..X.....X..X..X.XX.....X.X...........X.......X..X....X...X..X.X.X.X.....XX.X. ....X........X.XX......X.......XX.XX.........X....XX.X...XX............X.........X..X.X..X.....X... X....XXXX...X...X.XXXX...X.XX.......XX..XX.......X...X..........XX..X.X.X.X.X.X..X....XX...XX.X.X.. X..X.X....X..XX.XX.........XX.XX.XX.X..X...X.X.XX......X..XX..X.X.XXX.XX..X.....X.X.XX.XX...X...... .XXXXX.X..X..XXX.X....XXX.....X....XX.X....XX.XX....XX.X..XX.XX.XX.X.X......X...X.XX..X.X.XXX.XX...

Output

1826

Size 99 Test

Input

99 XX....X.X......X.......X..X.X..XXX.X....XX.X.X.X.....XXXX..X.XXX..X...X.......X..X..X..XXXXX.....X. XXX.X..XX.........XXXXX....X.X...X.........X.....XXX...XXX...X..XXXXX...X..X..X.....X..X.XX.X.X.X.. XXXXXX..X...X.X.X...X...XX..X....XXX..XX..XX...XXX.XX.XX..X..XX...XXX..X.XXX.XX.X..XX...XX.XXX..XX. XXX..X.XX.XX....XXXX..X....X.X.XX..XXX..X.X.X.......X....XX.....XXX..X.XX........XXX.XX...X.X.X...X .X..XXX..XX...X.X.X...XXX..X..........X....XX...XX..X...X.X..X...X.X.....X.XX.........X...X...X.X.. X.X.....XX.X..X.X..XXX..XXXXX..X...X.XXX.X..X...XXXX..X..X.XXX.XX..XXX...XXX....X..X....XXX...X.... ...XX........XX....XX...X.....XXX......XX....X....X.X..X.....XXXXXXX..X....X...X..XX.X...X......... X...X........X....XX.X.....XX.XX.X..XX.X.X.XX....XX..X.X...XX......X......XX.XX....XX.....X....XX.. X.XXX.X.X..X....X..X.....X...X..XXX.XX.X.X..XXX...X.X....X.XXX.....X.X.XXX.XX..X....XX.X.....XXX.X. .XXXXX...X....XX....X....X.X.XX...XXX....X.X....XX.XX.XXX.XXX.XX...X..XX.XXXX..XX..XX....X.X...XXX. .X.XXX...XX.........X...X...XXXXX..XX....X..X.XX.X..XXX.......XXXXX.X.X...XXX..XX..XXX.XX...XX.X..X ...XX..XX..X..X..X..X......X..X.XX..X....XX..X.....XXX.XX.X.X..X..X.X.XXXXXX.X...X.X.X.XX......XX.. .X..XX...X.XX.XXX......XX.X.XX..XXXX....XXXX.X.X....XXX..XX........X.XX.X..X.....X.X.....XXXX.X..XX X...X.XXX...X.X.X...XX.......X.X.....X..XX....X.X.X..XXX....XX.X.XX.X......XX..XXX........X..XX..X. XXX.X........X.......X.XX.XXX.X....XX..XXX..........XXX..X.XX.XXX.X.XX..X..XXX.XX..XX.X..XX....X.X. .XX.XXX...X.X....X.......XX.....XX....XXX.....X...X.XXXXXXXXX...X..XX..X...X..X.X.XX..XX.XX.XXXX... ....XX..XX.X...X.X.....X..X.XXXX...XXX......X.X.XXX.X........XX.XX...XX...X.X..X..X..X...XX.X....X. X.XX.X.XXX.XX....XX...XX..X..X...XXXXX.XX.X..XX.XX.X.X...XXX........X..X.X.X..X.X....XXX..X....X..X X.X.XX......XXX.X..XXXXX...X..X..X.XXX......X.XXXX...XX..X...X.....X..X.X...X.X.XXX..X..XX..XX....X X...XXXX...X.XX.X...XXX.....XX......XXX...X....XX........X.XX.X.....XX.....XX..XXXX...XXX.X...X..XX .XXXX..XX..X..XXXX.X.X...XX.X......X.X....X.....XXXX.X..XX...XX...X.X....XX..X...........X.X...XX.. ...X...X.XX.X...XX.X...XX....X......XXXX.X..X..X....X..XXXXXX....XXX.X..X....X.XX..X...X......XXXX. .X..X......XX....XXX..XX..XX.XX.X..X..X.X.XX.X..XX......X.....XXXX.XX..XX.XX.X...X.XXX..XX....X.X.X ..X......X.XX.XX...X.XX..XXXXXX.XXXXX.......X.XXX...X...X..XX.XX.......X.X...X......X.....X..XX.... .XXX.XX.XX......X..XX.X...X...X.XX.X.......X.X..X....X.XXX.......XXX..XX...XX...X.XXXXX..XXXXX..... .XX...X.X...X....XX..X..XXXXXX...X........X.....X.........X..X.....X....XXX.XX.......X...X......X.. X.X.X.XXX.XXX...XXXXX..X.XX....XX.XX....XXX...X..XX.X.X.X..XX.X.X...X.X.X.X.......XX....X.XX..X.... X.XX..XX....X.X...XX........X.X....X.XX.XX....X.X..X...X.X...X.X..X.....X..X.......X...XX...X.XXXX. .XX.X.XXXXX..X.X.........X........XX....X.X......X.X.X.X..X..X..X...X.X..XX..XX.XXX.X.XXX.X.X.X...X XXX.XXX.......X..XXX...X..X...X.X........XX.X.X.X..XXXXXXXXXXX..X........X.XX..X...XXXX......X.X... ..XXX...X......X..X.X.X....X.....X...X.X.X.X...XXXXX...XXXX.....X.X.X....X.X.......XXXX...X....X.XX ..XX...XX.X......X........X.X...X.X.X.X.X....XXX...X..XX...X.X.X.XX.X..X..X.....XXX...XXXXX..X..X.. .X.XXX..X...XX.X..X..XX...XX.X..X..XXX...XXX..X.X.X...XX.XX..X.X.............X.X.XXXX...XXX.X.XX... ...XXX...XX..X....X.X..X.X.X...X......X.X..X..XX..X..X...XXXXX.XX.....X.XX...X...XXX..X.X...X..XXX. XXXX.....X.X.X.X.X..X..XXX.XXX..X....XX..XX...XXX...X..XXXX.X..X....XXX..X..XX.XX....XXXX.X...XX... ....X.XXX.X...X.....XX.XX.X..X.X.......X.X.X.X.X...XXXXX.X..XXXXXX..XX.X.X...X.....X.XX..XXX....X.X X.XX..X.XXXX..X...X.....X..XX.X...XX.X.X..XX.....XXX..X.X...X..X...XXX.XX..X.X.X.X..X..X.....XX...X ....XXX.X..X...X........X.........X.XX..XX...XX....XX.XXX.X....X...XXXXXXXX.......X.XX.X...X....XX. ..X..X.X.....X.X.XXX.X..X...XX..X....XXX...XX.......XX....X..XX.X.X.X....XXXX..X.X..X.X.X..XX..X... .X.XX.X..XXX.X..X..X.XX..XX......X.....X.....X.X.XX.XX..X..X...XXXXXX...XX..XX.X.X.XXXX.X...X.XXXXX .XX..X.....XXXX...X..XXXXXX.X..XX........X.X.X..X..XX..X..XXX...XXX.X....X......XXX.X...X..XXXX.... ......X.XX..XXXXXX.XXXX.X.X..XX.XX.X.X..XX.X.XXX.....X...XXXXX...X.XX......X.X.X....XX.XXX....XX... ..X.XX.....XXX.X.X...X..X.X.........XXXXX.X....X..X...X.....X.X.X..XXXX.....X.XX........X.X...X.XX. ..XX.....X.XXXX.X.X..XX..X...X.X.....X.X....X.XXX..XX...X..XX.XX.XX.X.X.X...X.XX..XX....X.X.X....X. XXXX...XXX.X.XX.X.X...XX..XXXX......XXX....XX....XXX....X.X..XX....X.X..XX...XXX.XXXX...X.X....X..X X..XX.....XX.......X..XXXX...X.X.X..XX.X.X...XX..XXXX..XXXXX.X.......XX..X..X.......X..X...XXXXX.X. .XX.X....X.X........X....XX..X...X.X.X....XX..XX..XXX..X.X.X.X..XX.XXX...XX..X...X.X..XXX..X...XX.X .X.X.X.X....X.X..XX.X......XX....XXX..X.X.X.X.....XXX.X.X.......XXXX..XX.......X...XX.X..X.XXX..X.X XX....XX...X..X...XX..XX..XXX...............XXXX....X.X.X......X...XX.XX.X..X.X.X.X.X..XX...XX.X.X. ......XXX.X...X..X.X.X.X...XXXX...XXXX....X.X.XXX.....X......X.X..X..XXX.........X...X........X.X.X X....X.....X...X.......X.X.X...X..XX.........X...X.XXX..X....XX.....XXX..X..XX...X..X..XXXXX....X.. X.X.X....XXX..X....XX..XXX.X..XX..XX..X..XXX..X....X.XX.......XXX.X.....X.X..X....X....X........... X.X....X....XXX.XXXX..XXXX...X..XX.....X.XX....XX..XX.X.XX.XX......X.XX.XX..X....X..XX..XX.X....... .X...X...XX..XX...X..XXXXXXXX...XXX.X.XX..X.....X...X.XX..X.X.X.....X...XXX.XXX....XX.XXXX..XXX.X.. .X...X.X..X...XX...X.X....X.X..XX..X.....X...X..X.X....X....XXXXX.......XX.X....X..X....X.X..X.X.XX X.XX..XX.XX.XXXXX......X..X.X...X..X..X.X.XX..X...XX.....XX.XX.X...X..XX...XXX.XXX.X.X.XX.X..XX.... X..XX.X.X...XXXX.X....XXX....XX..XXX.XXXXXX.XXXXXXX....XXXX..XXX.XX.......X..X.......X.XXX....XX.X. ..X..X..XXXX..X...X...X...X...X.XX..X..XX.....X.XXXXXX.XX....X..XX...XX.XX..X......XX...X.......... .X....XXXX.......X..X......X..X......XXX....XX.....XX.X..XX....XX..X.XXX.....XXX.....X.XXX..XX.XX.. .XX.XX.X..X.XX.XX..X.XXXX..X...X..XX..X.XX.X.XXXXX....X..XX.X.X....X....X.X.XXXXX.XXX....XXXXX.XX.X .X..X...X...XX.XXX....XX.X.XXX..XXX.XX.X..XX.......X......X.X...X...XXX.XX..XXX..XX.......X.XXX.X.. XX.X.XX.XXX........XX.XXXXX.....X.X..X.....X...X.....X..XX....X....X.X.........X....XX...X.X.X.XX.. XX.XXXX........XX......X.X..XX...X..XXXXXXX.XX.......XX.X.XX.X..X.X.XX...XX.XXX.XXX...XXXXXX..X...X ...X.X.XX.....X.XX.XX..XXX.X.XX..X..X....XX.X.X...X..X..XX......XX.X.X....XXXXXXX...XXX..X....XXX.. .XX..X..XX.X.X....X.X.XXXXXXXXX..XX......X.X.X.XXXXXX.X....X.X..XXX.X.X..XXXX.........X..X.X...X.X. XXXX.X..X.X.X..XX..X.X..X.X.XX.X.X..X.XX...XX..X.X..XX.X.X...XXX..XXXX..XX..X...XX....X...XX.XXXXXX ...X.X..X..X.........XX......X.X......XX.X..X........XXX....X.....XX.X..X.....XX..X...XX.X..X.XXX.. ......X.X...X....XXX...X..XXX.....XXXX.XX....XX........XXXX..X.X...X.XXX...X....XX....XXX..XX..XX.X XX......X.X.XXX.X...X...X..X.......X.X.X.........XXXXX....X..XX......XX.X......XX....XXXXX.X...X.XX ..XX..X..XX..X.....X....XXXX.X...X..XX.......XX..XXXXX...XX..XXX...X....X..X.....XXX..X.....XXXX..X .X.....X.XX.XX.....XX.X.XXXXXXX....X...X..X..X......XX.X..X.X...X.XX...XX...X.XXXX.X....X.....XX..X .XX.X..XX...X...XXX..XX..X....X..XX.XX.X.XX..X.X..XX....X.XX..X......X..........X......XX.X....X.XX X..X.X...X.X..X.XXXXX...X.....XXX.XX.XXX...XX....XX...X.X......X.X..X...X.XX...X.X..X..XXXX..XX..X. X.X..X..X....X....X....X.....X..X.XX.X.X...X...X.....X...X..X....XX....X.X..XXX..X.....XXX.X..X.XX. .X..XX.X.XXX.....X..X..X..XXXX..X............X..XX..X...XXXX......XXX.....XX.X...XXX..XXX...X....XX X.XX.XX..X.XXXXX..X.X...X..XX.XXXXX.X..XXX.....X.X.......XX.X.XXX...X.....XXXXX..XXXXX.......X.X... ........X.X.X..X.XX....X....X......X...XX.XX.X...X......XX..XX..XX...........XX.X.X.X.XX..XX....... ....X.XXXXX..X...X..X.XX.XX.XX.XX..XX..X..XX.......X.........XXXXXXX...X.X..X.......X.X.......X...X XXXX..XXX..X...XXXX..XXX...XX.XX..X..X..X....XXX.XXX..X..X.X.XXXX..XXXX..X.X......X....XXX.X..XX... X.....X..............XX.X.XX...X..X..XXX.X.X.....XX....X..X..X.XX.X...X..XX...XX.X..X..XX..XXX..X.. .X..XXX.X.X.XXXX....X.XXXXXX..X...X.X....X.X.......X.XX.X.....XX..XXXX...X...XX..X.XX.XX.....X.X..X ......XXX.XX.X..XX..X..XX..X.....X.XXX..........XX.....XX...XX...X.X......XXX...XXXXXXX.XX..X.....X .X..XX.X...XX.X..XX....X.X...XX.XX.XX.XX....XXXX...X..X..X..X.X.XXX.......X.....X......XX.X..XX.... X.....XXX..X...X..X....XXX.XX..X..XX.....X..XXX.X...XX...X....X.XXXXX....X..X.............XXX.....X XXX.XXXX...XX..XX....X.XXXX..X......X......XX....XXXX.XX...X.XX...XX..X.X..X..X...XXXXXX.X....X..XX .........X...X.....XXXX..X...X..X...............XX..X....X..XX.X.XXXX..XXXXX.X..X..X.X.....XX.XXX.X .X..X.X.....X.X.XX..X..X..X...X..XX..X.X.....XX.X...XX.X.....X..XXX.X.......X.X.XX..X......X.X.X... X.X.X.......XX..X...X...X.XXX.XX.XX.X...XXXX.X......XX.....XX..X..XX.....XX...X....X.X..X.X.X..X.X. .XXX.XXXXXXX.X.X...XX.X..X.X.X........X...X.X....X.XX.XXX...X.X....X.XXXX......X...X....XX.X..XXX.X X.......X..XXX..XX..XXXX...X..X.X.X.XXX..X..X...X..X...X.XX.....X..X.X..X.X.XXX..XX.XX.......X..XX. ......X...XX..XX..X.X......X....X.XX.X.XXXXX.....X..X.X...XX...X.X...XX.......XX..X.X....XX...X.X.. .X.XXX...........X..XX..X.X....XXX.XXX.X.XXX.X.XX.X.X.XXXX...X.XX.X.X..X...X..XXX.X.XX...X....X.XXX .X.X......X..X...XXX.XX.......XXXXX..X.X..X.XX.X....XXXX.....X...XX..X..XX.XXXXX...X.X.X..X.X..XXXX .XX....X..X.X..X..X.X.X......X..X...XX.XX....XXX.XX.X..X..XX.....XX.XX...X....XXX......X....X...XX. XX...X....X..XX.....X.XX.......X.....XX.X.XX...X..X.XX..X..X....X..XX...XXX.XXX.........X...X.XX.XX XXX.....X.XX.X.X..X.XX..XXXX.X.X......X..XXX.....X..XX...X........XX....X.X..X.....X.XXXX..XX.X.... X..X.X....X.XX.X....XXXX.X.X.X.X.XX.XX...X.XX....XX.....XX...X.X.........X..XX...XX.X...X....X...X. X....XXXX.....XX..X......X..X.XX.....XXX....XX..X........X......X..XX.X.XX......XX..X...X......XXX. ...X.....XX..X..XX......XXX.X.X..X...X..X.X..X......XX.X...XX...X..XX..X.XX.X.X...XX...XX........X.

Output

2018

Validator 7 Validator

Input

99 XX.X..X.X.XXXX...X.XX.XXXXX.X...X....X.....XX..X.X.X.X.....X...XX.XX..XX..XX....X..X...X.X.X.XX..X. X............X..X..X.XX.X.X...X...XX....X.XXX.X.XXX.X.XX.XX......X..XX.X.XXX...XX.XX...XXXX.XX..XXX XXX...X.XX.....XX...X.X..X....X.XX.XX.XXX..X.X...XX.XX.XXXX.XXX...XX..X..XX....XXXX..XX..XX..XX.XXX XXX.....X.X..X.....X...XX...X..XX....X....X..XXX.XX..X.X....XX...X.........XXX....X....XX..XX...... X..X.X..X...XX.XXX..XX.....XX.X.XX..X....X..XX....X..X.....X.X...X..XX....X.....X.X.....X.X..XXX.XX XXX.XXX.X.....X.XXXXX.X....X..X..X......XX..X.XXXXXXXXX..X..X..X.X..X...X..X..............X.XX.X.X. XX...X....XXX.X..X..X.X...XX...XXXX.XX.XX....X....XX.X.XX..XXX.......XXX....X.X..XXX.XXX.XX....X.X. .XXX.X.X.......XXX...........XXX.XX...X..XX...XXX...X.X.X...X..XX.X..X..X.....X..XX...XXX.X..XXX..X X..X.XX......X.XXX.X....X......X.....X.X..X.XX...XX....X.XX.X.......X...XXX...X.....X....XXX......X XX....XXXXXX..X.XX..XX...X..X...X.......XXX..XX..X.XX..XXX.XXXX.XX.X.X.X.XX....X..X......X.X....X.X ..X.XXXXXX.XX.........X......X..X.X....XX...XX.X..XX...X.X..X....XX....X.XX.XX...X....XXX...XXXX.X. XX.X...X.....X.X....XX.XX.X..X..X..X..X..X.X.........X..XXX.........X.X.X......X.XXX...X......X.... X..X...X.XX..XXXXXXX..XXX.XX.X.XXXX...XX.X..X.X..XXX.X...XX..X.X...X.XXX.X.....XX.XX........X..X..X XXX............X.X..X.X..X..X.X........X..X.X..X.XX..X....XX...X..X..X..X....X..XX.X....XX......... ....X....XX.XX.X.......X..........XX.XX.XX..XXXXX.XXX..X.......X.X..XXX.X.X.XX....X.X.....X..XX..XX XX...XX...X.X.XX.XXXXX....X......XX...XXX...X.X..X.X.....X...XXXX..XX.X....X......X...XX.X..X..X... ..X..X.....X.X...XXX....X....XXX.X...X.X.XX.....X.XX...X....X.X..X......X.XXX....XXX.X.XXXXX.X..XXX .X.XX..XX.X.XXXXX......XX.XX.X.X....X.XX.X.XX.X.X...XX.....X.......XXXXX..XX..X...X.XXX.....XX..XXX X.X...X......X....X.X...XX..X..X.X.X...X..X.X.X.X.XX....X..XX.XXXX..X.XXX.XXX.XXXXX.X.XXX..XX.XXX.X XXX..X..XX.....X........X.X......X.....XX.XX..X.XX...XXX.X...X.X..XX.....X..X.XX....X.....X..X..X.. ..X..XX.XX..X.XXX.X..........X.X..X.X.XX.....X...X...X...X.X...XX.XX.X...X.X...XX..XXXX.X.......... X....X.X..X..X.X.X.X.X...X.X.XX..X.XXXXX.XXXX.X..XXX...XX......X...X....X....X.X..X..XXXX.....X.... .X.X....XX.XX.X.X...XXXXX...XXX..XX..X..X..X.......XX.XX.XXX.....XX..XX.X..X..X.X..X.X...XXX.X.X..X .....X.XX.X.X.......X.....X.....XX.XX...X........X...XXX.XX.X...X.X.XXX..X...XX......XXXX.X....X..X ..XXX..XXX....XX.X....XX......XX.XX.X.......XXX...XX.X.XXXX.....X..XX....X..X...X..X..XX....XXX...X .XX.....X...XX.XXXX......X..XX..X..XX...X.....X.XX....XX..XXX.X.X.X...X.XX.X..XX..XXXX.X...X...XX.. .X....XXXX.XXX.X.X.XX...XXXX..XX.....X..X.X..XX..XXXXX...X...X.X......XXX...XXX...XX.....XX...X..XX X....X.X.XXXX.XX..X...X..X...X...X........X..X..XX.XXX.X.....XX...XXXX.XX.......XX...XX...X..XX.XX. ....X..XXXXX...X..X....X.X.....XXX.XXXX.....XXX.X.X.X..X.....X........X.......XX.....X....X.......X .XX...X.X.X...X.....X.X.XXXXX.XXX.XXX.X......X..X...X.....XX..XX..XXXX..X......X..X......XX....X... X.X....XXXX.XX.X........X.X.X.XX..X.XXX...X...XX.X.....XX....XXXXXX....X.XXXXXX..XXX.X...X....X.... X.X..X.X.XXX.........X..XXX..X.....XX..XXX...X.X..X.X.X.XX....X.XX.XX.XX..X.X...X.XXXXXX.XX...XX... XX.XXXXX.X..X..XX.X..X....X..X.XX.X.XX...X.....XXX.XX.X.X.X...XX...X...XX.X..X.XX....X.......X.XX.. ....X.....X.X...XXX..X...XX...X...X.X..X.XXX..XX.......X..XXX.X..XX...X..X...XXXXX.......X..X....X. .....XX.X...XXXX....X.....X....X..X...XX.X..X......X.X..XXX..XX.X..X..XX..XX....XX.X.X.X...X.XXX... XXXXXX...XX...XXX...XX...XX.X.......X...XX..XX.X..XX.X.X....X.X.......X..XX..XXX.XX..X.XX.X..X...XX .XX..XX.X..X........XX..XX.XX.XX....XX.X.XX......XXXX.X.X.X..X.XX.XX.X...XXX.X...XXX.X.XX..XX..XXX. ..X..XX....X.......X..X.X.XX.....XXXX......X.XX..XX...X.....X.XXXXXXX....XX....XX.X.X..X.XXXXX..X.. ...X.X.XXXXXXX.....X.X...XX.XX..XXX......XXXX...X.X....XX...X...X.X.....X.XX...X..X..X.X.X.XXXXXXX. .XXXX.....XX..X..XX.X....X........X.X..X..XX..XX.XXX....XX.X....XXX.....XXX.X...X.....XX..XX.XXX... .X.X.....X.XXX..X.XXXXX.XX.X..XX.X.X.XX...X....X...XX.XXXX......XX.......XXX..XX.XXX.......X.X.XX.. .XXX...X.X....XXX...X....X....XX..X.XX.X.X.X.......X..XXXX..X...XX.....X..X....X......XXX.XXXXXX... ...X....XXXXXX..XX.XXXX.XXXXX..XX.XXXX.XX..X.X.....X.X.X.......X.X.....X....X..X..X.X.X.X...XXX.... ....XXX.X.X..XX..X..............X.XX....XX.X.XX.X.X.X..X..XX....XX.XXXX..X.X...X.XXX.XX.....XXXXX.. XXXX.XX.....X....X.X.....XX..X..XX.XX.XX........X.XXXXX...X..XX.X.X.XXXX..X.....XX...X.XXXX....XX.X ....XXXX.XX..XX.X.XX.X.X....X.X.X.XXXX...X.XX.X....X..XX.XX.......X.....XXXXX..X...X..XXXXXX..XX..X ..X..X.X......X.X.X..X..X....X..X.X....X...XX.....X...X....XXX.XXX.X.........X.X...X...........X... .XXX...X...XX.X...X......X...X........X....XX.X.XXXXX...XX..XXX......XX.XX.....X.XXX.X.X.......XX.. XX.X...XXX.XXX..XXX.XX..XX.X...X.X.X.X..XX.XX.X.X.XX...X.....X..X..XXX.X.XXX.XX.....XX.XXXXX.XX..XX X.X..XX..X.XX.X...X.X.X.X.X.XX.XX..X..XXX.XX.X..XX..XXX.....XX.XXX..XX..X.....XXX.XX.X..........X.X XX...X...X.X..X.X.XX.....X....XX......X..X..X..X...XX....XX.XXX.X..XX.XX..X.XX....X...X...X.X...... .XXX.XXXX...XXX....XX..X.X.XXXX.X...X..X.....X.X.XXX.X...XXXXX.X.....X..XXXXXX..X.......X..X....XX. ..X.X..XX..X.....X.XXX.XX.XX.XXX.X.X....X..X.X.X..X...X..X.XX.X..X....X...XX.XX....XXXX.X..X....XX. X.X..X.X.XXX........XX....X.X...XX.XXX.XXX..X......X.X..XXX..........XX.X.XXXXX.XX....XXX...X.X..X. X.X.X.XX.....XXXXX.......X.XX..X..XX.X..XXX...X.XX.X....XXX...XX...X.X.X.X.XXX.XX...X..XXX..X...... .XXXXXX.XXX..X..X.XXXX....XX..XX....X.X.X.........X.....X.....XX.X.X......X..X.XX.XX............XX. ..X.X...XX.XXXXXXXX....X.XXXXXX.......X.......X.....XXXXXX...X.....XXXX.X..X....X.X.XX...XX...X.X.. X..XXX.X..XX.X..X..X..X....X..X.X...X..XX....XX.XXXX.XXX...X.X..X..X.X.X...X...XXXX.X..X.....X..X.. .XXXX..XX.XX.X...X...X.X..XX.XXXXXX......X..X.X..X......XX.X....X...X..X..XXX...X.XXX...X.X.X.X...X .....X...X..XXX.XXXXXX...X.X..X.....XX..X.XXX......X..XX......XXXX.....X.XX..XXX...X.....XX..X.XXXX .........XX.X.X......X.....XX.X.XX.X..X..XX...XX.....XX..X.XX.X...X........XX...X..X........X.XXX.X X.....X...XXXXX.X....X.XXXX.XX...XX..X..X.X.XX.X.......X.X.X.XX.X..X...X.X.X.X..XX..X...XX.X.X...XX XX....X.XX.X....X.XX.X.X...X.X...X.X..XX.X....X.X.XX...X..XX.....X.X....XX.XX..X.X...X.....XX...... X.XXX..X..XX.X.X.XX....XXX...XXX...X..X..XXX..X.X...XX....XX..X.X..XX.X..X..XXXXX.XX...X..X..XX.... ...X...XXXX...XX..X.....XXXX..X...X...X....X...X..X..X..X.X..X..X.X....X....X.X..XXX....X.XX......X ..X.......X.XX....X..XXXXXX.X...XXXX.XX.....XXX.X.XXXXX.X.XXX..X..X...X...X.XX..X.............X.XX. .X.....X.X.X...X..XXXX.XXXXX.X.X..X.X..XX....X.XX..X.....XXX...X....XXX.XX..X..X...X.X.X.......X... .X..XX.XX.X.XX...X.XXX..X..XXX.....X.XXXX...XX..X.XX...X..X.X.X.X..XX.X.X.XXX.......X..X......X.X.X ....XXXX..X..XX.XXXX..X.....XX.....XX.....XXX.X.XXXXX.X.X......XX.XX....X.....XXX.X.X...XX.XXX..X.X X.X..XXXX...X.XXXX....XX...X.X.X.XX......X.X...X.XXX.X.XX..X..X...X...X......XXXXXX...........XXXX. X...XXX.X...XX....X...X....X........X.X.X..X....X..XXXX.XX.XXXX....X...XX..XX.XX...X..XX......X..XX X.....XX...XX....X.....XX..X..X.X.XXX...X...X.X......XXX.XXX...X...XXXXX..X....X...XX.X...X....XXX. ..X..X.X...X.XXXX..XXXXXXXXX.....X.....X...X.X..X...XXX....XX..X.X..X.X..X.X....X.XXXXX..X....XXXX. ..X.XX...XX.X......X.....XX.X.XXX.X.X.X.XX...X...X.XXX.X.X....X..X....XX...X.XX.X.XX..X..XXX..XXX.. XXX.XX.XX..XXXXXXX..XXX..X..X....X.X.XXX.X....XXX....XXX...XX.X.XX...XX.....X.....X......X....XX... .X..XXX.X....X......XX.X...XX........X....XX.XXX..XXX.XX.XXX.X.....X.XX....XX.XXXX.XXXX..X..XX..XX. X.XX.XXX....XX..XX.X.X.X..X.X............XXX.X.XX...X.XXX.XXXX....X...X.X.....X..XXX.....XX........ .X...X..X..XXX..XX.X..XX..X.X....X..X.XX.XX.X.X...XX..X..X.XXX........X.XX...XXXX.X......X....XXX.. .X....X.X..XX....XX.X.XXXXX.X...X..X.XXX....X............XX...X.X...XXX.X..X.XXXXX.X.X..X.X.XXX..XX ......X.XX....XX.XX...X.XXX...X.X.XX......X....XXX..XX.XX..XXXX....XXX...XXX...XX..X.....X.XX...XXX .X..X.XX.......XX.......X.X....X.X..X.X...X..XX..XXX.X..XX..X....XXX.XXX......X......XX.XX....X.XXX ...XX...XXX...X.X..X...........X.....X.X..XX....XX..XX...X...XX.....XX.X...XX.......X.X..X.X...X.X. ...X.X...XX.X.....X....XX....X...XX.XX..X......X...X............X..X.X..X..XXX......XXXX.XX.X....XX .X.XXX.XXX.XX.....X...X...X....X....X..X.....X...XXX.XXX.XXX...X..X...X.X.X.X...XX.XX....X.XX...X.. .XX.XX..X.X..X........X..XXX.X...X..XX....XX.X....XX....XXX.XXX.XXX....X.XX.XX....X.....X.XXX.X..XX XX.XX.XX....X....XXXX....X.....XXX.XX..X.X.XXXX.X.XX..X..XX..X..XX..X..XX.XX..X..XX.XXX..X...X..X.X X..XX..X.......X..X.X....XXXXXXXX.....XX.XX.X.....XXXX..XXXX...XX.X.X.X..X.......X.X....XX.X......X X.XXXX.XX.X.X.X.X..XXXXXX..X......XX.X.....XXXX.XXX....X...X.X.XX.X...X.X.X..XX.X..X.XX.X......X..X ....XXXX.X.....XX.XXXX...XXXXX.XX.X.XXX..X.X...X.X.X.XX.XX..X.XXX....XX....XXXX.X.XXX.XXXX...XXXXXX ...XXX.X....X.XXXX.X.X.X.XXX..X..X....XXX.XX.X..X.XX...X.X...XXXX...XX.XXXXX..XX....XX...X..X.X..XX XX.X...X.X...XX...XXX.X.X..X...X.XXX..X.X.XXX.....X.X..X......X.....XX.X..X...XX.X..XX.X.XXXX..XXX. .XX.XX..X...X...X.X....XXXX...X.XX.XX.X.X.....XX...X..XX...X..X...X...X..........X..X....XX.X...... .X.X..XXXX....X....X.....X...X.....XXXX.....XX...X.....X....XXXXX..X..X..X.XX.....X.XXXXX.XXXX.X..X .......XX...X.XX.XXX..XX...X.X..X......X..X.X.X............X.X...XX...XX.X.XX.XXXXXX.....X.X.X..X.. X..XX..XXX..XXX..XX....XXX..XXXX...XX..XX........X...XX.X..X.X..X.X.XX.X.X.....X..X.XXX..XX...XXX.. .X.......X.X...X.X...XX.XX........XX..X....X....XX..XX....X.....X..X.X...X...XX..X..XX.X..X..X..XXX ....XXX..X....X......X.....XXXX.XXX.XXX..X.X...X..XX....X.....X..XX.XX...X.X..X.X.X...XXX...X.X.... X.XX..XX.X.............XXX.X.XX.X.....X..X..XXXX....X...X...X.X.......XXX......XX.XXXXXXX..XXXX..X. ....XXX.XX....XXX.X...X..X.X.X.......XX.XX...XXXX.X..X..X.XXX.....X...X.X.....XX......XX....X.X.XX.

Output

2055

Size 99 Test

Input

99 X...X...XXX.X...X.X.X....XX.XX.XX..X...X..XXXX.XXXX..X.X.XXXX.X.X...X..XX.XXXXX....XX...X...XXXX.X. ..XXXXX.......XXX.XX.XX.XXXXX..XX..X.XX.XX.XXX..X.X..X.X.XX...X..X.X....XXXX..X..X..XXX..XXX.X..X.X XX..XXX.XX.X..XXX...X.XX.XXX.XXXXXX.....X..XX..XXXXXX..X.X..X.......X..X..X.X.XX...XX.XX.XXX..X.XXX ..X.XXX..X.X.....XXXX..XXXXX..X.XX..XXX.XXXX...XX....XX.X.X.XXX..X..XXX..X.X.X.X.XX.XXXXXXXXX.....X XXX.XXXXX.XXXX.XX..X....X..X.X.X.XXXX.XX.X..XX.XX.......XX.X...X........X.X..XXX.....X.XX.X.X...... XX.X..X.X...X.XXXX......X.XX.....X.....X..XX.X.XX..X.X.X.X...XX...XX.......XX.XXX.XX...X...X.X....X ..X.X..XXX.X.XX..XX..XXX...X.X.XXXXXXXX..X.X...XXX.XX...X.X..XX..X..X..XXXX.X.XX..XX...XXX.XXXX.XX. X...X.XXXXXXXXXX.X..XXXX.XXX..X..X..XXX..X..X..X....X..XX..X.XXXXX..X.X.XX...XX.X..X..X.X.XX.XXXX.X .XXX.....XX..XX.XXX.X.X...X..XX............XXX.XXX..X.X...X..XX....X.....X.XXXXX..XX.X.X.XXX......X XXXXX.X.XX....XXX.XXXX..XX..X.X.X.X.....X.X..X.X.XXXX.X....XX...X..XX.XXX.XXX..X..X.X.X..XX.XXX.X.. X.X....XX..XXXXXX..XXXXX..XX..X.X.......X.X...X..XX..XXX.X.X...X....X..X.X.XX.XXXX...XX..X.X.X...X. .X.X...X.XXX.X.X.X.X.X......X.X..XXX.XXX.X...XX...X..X.X....X..X.XX...XXXXX..X.X.X.....XX.....X.X.. ....XXXXX.XXX.X...XX..XXX...XXX.X.....X..X....XX..X....X.XXXXX..X...XXXX...X.XX..XXXXX...X..X.XXXX. ........X.XXX...X.X.XXXXXX...XXXXXXX.....XX.XXXXX.......XX.X.....X...XXXX....X.X..XX..X..X.XXXXX... XX...XXXXX.XX...XX..X...X.X.X.XXX..X.X..X..XXXXXXX..X.X...X.X.X.X...XX.XX......XX.XX...XX.XX..XXXX. ....X.X.XXXXX...XXX...XX.X.X.XXXXXXXX.X.XX...XXXXXXX.XX..X.X.X.XX..........X.X..X.....X.X.X.X.X...X X....XXX..XXX...X..XXX...X....XX.X..XX..XXX.XXXX..XX..XX......XX.X.X..X....X.XX...XXXXXX..X.XX..XX. .XXX.X..X..XXX.XX.X.X.XX...X...X..X....XX.X.X.X.XX..XXXXXX..X....XX....XX....X.XX..XXX...XX.X...X.. X.X.X.XX..XX.X.X.X..X..XXXXX.X.XX....XXXXX.X........XX.X..X....X...X.....X..XXXXX.....X.XX..X.X..XX .X.X...XXX..X....X.XXXXXX.X.XXXX.X.X.XX.XXX.X....X.XXXXXXXXX...X....XX...X.XX.X...XX.X..XX.X...X..X XX...X...X..XX.XX.XX....X.X.X..X.XX.XX.XXXX.X.X.XXXX..XX...X.X.....XXXXX..X..X..XX..X.X.X..X..XX.X. .X.XX..XX....X.X.X.XX.X.X...XXXXX..X..XX.XXX.....X.X.XXX..X.X...XX..XXXXX.X..XX.XX.XX....X.X.XX.... .XXX..X.......X...X..XXX..X.XXX.X..XXXXX..XX..XXX.X....X.X..X.XX.XXX.X....XXXXXX..XX.X.XXX.X.X.XX.X XXX.XXX..XXX..X.X.X.X.X....XXXX.XX.XX.XXX.X.X....X.XXXX.XXX..XX.X.X.XXX.XX......X.X.X.XXXXX.X...X.. .X.X.X...X..X.X.XXXXXX.X....XX.XXX.X..XXX....X.X.XX..XXX..X.XX....XX...XXXX..XX.XXX.X.XXX..X......X XXX.XX.X...XXXX..X..XX..XX.......X.X..XXX..XXX..X...XX....XXXX...XXXX.X...XXX....X...X.X.XXXX.X.XXX .X.X.XX.X....X...XX.XXX..X...X..X.XX.X....XXXXXXX....XXXXXX.XXXX...XXXX..XXXXXXXX..XX.XX...XXXX.XXX X.X..XX.X.X...XXXX.XX...X......X.X...XX.XXXXX.X..XXX.XXXXX.....X...X.X.X...X...XXX.XX.X.X.X..XXXXX. .XXX.X...XX..X...XX.X.X.XX.XX.XX..X..XXX.XX..XXXX..XXXX......X...X.XXXXX...XXXX....X...X....XX..XXX ...XXXXX..XXX...XXXXX.XX..X..X.X...X.X.XXXX..XXXX.X..XX.X.XX.....XX..XXXX...X...XX...X.XX....X.X.X. X..X.......XX.XX..XX..X.X..XX.X.XX.X.X.XXXX..X..XXX..X..X....X.XXXX.XXXX.XXXX.XXX.X..XXX..XX.X..XXX XX....XXX.XXX.X.XX.XXX.X.XXXXX.....X.X..X.X....XXXXXX..X.....X..X...X..X......X.X.X.XXXXXX.....X.X. XXX.X...XXX....X...XX..XX.XXXX.XX....X.X.X..X.X.XX.XX.X..X..XXX.XXX.XXX..X.X.X..XXXX.XXX..XXXX.X..X X..XX..XX..XXXXXXX..X.X...X.X..XX..XXXX.XX...X.X..X.X..XXX.X.XX.X....XX..XX.XXX.X.X......X.X...X.X. .XXXX.X.....XXX.XXXX.X..X..XXXXXX...XXX.X.XXX...X...XXXXXXXX..XX.X.X.X.XX.X.X......X..XXXX...XXXX.X X.X...XXX.X..X....X...X.X...X.X.XX.X..XXX..X..XX.XXXX.X.X..X.X...XX.X..XXXXX.XXXX..X..XX....XXX.... ..XX..X..X....XXX...XXX.X.....XXX.X..XXX.....XXX..X..XX..X.X..XX..X.XX.X..XXXXX...XXX.X.XXXX..XX.XX .XXX..X.X...X...XXXX.XXXXXX.X.....X.XX.X.X...XXXXXXX..XX.X..X.XX..X..XXX.X.X...XX..XX.XX..XX....... ..XX..X..XX.XXX.XX...X.XX.XXXX...X.XXXXXX...XX...X..XX...XX.X..XX.X..XXXXXX.X.X.XX.XX.X......XX.XXX .XXX.XX..XX....XXXXX...XX.X.....X..X...X..X...XXXXXX.X.XXX..XXXX.X.X.....XXXX.X...X.X.X..X....XX.XX ..XX.X.X..X..X...X...XX..XXX..XX.XX..X.X..X..XXXX.X.X..X.X..X..X.....XX.X.XXX...X.X.X.XX.X.X.XXX.X. X.XX....XX...XX.............XXXX.X.X....X...XX.XX..X........XXX...XX.X....XX.X.X.XXXX.X..XXXX..X.X. ...X.XX.X..X.XXX..XX...X.XX.X.X.X..XX.X.X.XX.....XXX.X..X......X....XXXX.....X.XX..XXXXXXXX........ .XXXX..XX..X..XXX......XX...XXXX...XX.X.X..XXXXX.XXXX..X.X.X..XXX..X.X.XX..XX..XX..XX.XXX.X...X...X ......X...XX...X..XX..X.X.X.XXX.XX...XXXXXXXXXXX.XXXXXX...X....X.XXX.X.XX.X......X..X...X.XXX.X.... .X..XXXXXX.XX.....XXXXXX.X.X.XXXX.X.XXXX.X..XXXX.X.X.X..XX.XXX.............XXX...XXXXX.XX.X.XX..X.. XX.....X.XXX....XXX..X...XXXX..X..XX..X.XX.X..X....X....XXX..XXXXXX...X..XXX.XX.....XXX.XX...X.X.XX XX.X..XX..X.X..X.X.XX.X.X.....X.XX.X.X....XXXXX.X.....X..XX.XXX.XXXXXXX.X.X..X.....XX...X...X....X. X.X.XX...XXX..X........XX.XX...XX.X.X.XX..XXX..X.......X.XX..X.X.X.XX....XX...XX.XX...XX.X.XXX.XX.. X...X.X..XX..X.X....X..X..XXX..XXX..XXXXX.XXX.......X.X....XXX.XX..X......XX..X..XXXXXX..XX..X.X.XX XX...XXX......X.X.X.X.X...XX.X.......XXX.X.X...X.XX.X.XX...XX......XX..XX....X..XX....XXX..XXX.XX.. XXX..XXX.XXX.X..X.....XX.X....XXX.XXXX.X.X.X.X.X......XXX..XX...XX.X.X.XXX..XXXXXX.XX.X..X..X.XX..X ..X....X...X....X.X.XXX..XX.XX.XXX.X..XX..XXXXX...X......X.X.X.X.X..X.X.X.XX...XX.X.X.XX.XX...X.X.X ..XX.X...XXXX.XXXX.X.X.X..X..XX...X..X.........X.X....X.X.XX..X........X....XX.XXX.X..X.X.XX.X.XX.. ..XX.XXX......X...X.X.....XXX..XXXXX.XXX.X.X.XXXX..X..X....XXX.X.XX.............XX.XX.XX.X..XX..X.X XX....X.XXX.XX.XXX.X...XX.XXX.XX..XX..X..X.XXX..XX....XXXXXX.X.....XX.XX...XXXXXXXX..XXX...XX.X.... X..X.X..X...XX.XXX.XX..XX.X...XXX.XX..X..XX.XX...XX..XX.X...X.XXXX.XXX..X.X.....X..XX.XX..XXX.....X .XXX...X..XXXX...X..X..X..XXXXX.XX.XX....XXX...XX...XXXXX.XXXX.X.....X.X.....X...X..XXXX.X..XXXX.X. X..X..X............XXXXXXXX...XXX....X..XXXXXX.XX.X.XXXXX..XXXX.X.XX....X.X...X.X.XX.X..XXX..X..... X...XX.....XX..X....XXXXXX..X.X.XX..X.XXX.X..X.X.X..XXX.X...X.X..XX..XXXX..X.XX.XX.XXX...X.XX..XX.. ..XX.X..XX.XXXXX.X..XX.X......X.X...X..XX.XX.XXXX..XXX.X..XX.X.XX.X..XX.X...X..X...XX....XX.XX..XXX X.XX.X.XXX..XXXXX.X.X.X...X.X.........X.XXXX...XXXX..X..X..X.....X.X.X.X.X.XX.X.XXX.X...X.XX..X.X.X .XX.XX.XXX.XX.X.XXXX..X.XX..X.X.X...X..X.X.X...X..X....XXX..XXXX.X.X..XXX...X..XX..X.XXX...XX.X.... XX..XXXXX.X...XX.........XXXXXXX.XXXX.....XX.X...XX.X.X.XX.X....X.X.XX.XX.X.XX..X.X..X..X.XX.X..XXX ..XXX..XX.X..XX..XXXXXXXXXX.XX.X.XX.X..X..X.X..XX..XXXX.XXXX.XX.X.X.X...XXX..X.X.XXXX..X..X.X.XX.X. X.X.XX..X..XXX.X..XXXXXX.XXXXX...XX.XXXXXX.XXXX..X...XXXXXXX.XX.XX...XX.XX....XXXXX.X.XX..X.XXX..XX .XX.X...XXXX...XX.XXX.X..XX.XX..X.XX..X....XXX.XXX.X...X........X.X...XXXXX.X...XXXX.XX.X...XXXXXXX XXX.XX.X..XX..XXX.XXXX.X.X..X....XXXXX...X.XXXX..XX.XX...X.XXX....XX.X.XX..XX...XX.XX..XX.X..X.X..X .X...X.X.XX.XXX.X...X.X...XXX.XXXX...X....XXXXXX.XXXX.X.X....XXXX..XX..X..X.XXX...X.XXX.XX.XXX.XXXX ..X.XXXXX.X.XX.X.X.X..X.XX......X.XXX.XX.XX...X...XXXX...X.X..XXXXXXXX.X.XX.X..XXXX....XXXX....XXX. .XXXXX..X..X.XXXX...XXXXX.X.XXX..XXX.XX.X.XX..XX..XXX.XXXXXXXXX...XXXXXXXXXXX...X..X.......XXX...X. ...XX.X..X.X.X.X.XX.X..XXX..XX...X....XX...X..XX......XX.X.XX.X.....XX......XXXXXXXXXXX.XX.XXXX.X.X XXX..XX..XXXX.XXXXX....X...XXXXXX.XX.XXX..X.XX......X....XX....XX.XXX.....X..XX..XX.X.XX.XX.X.X.X.X XX..X.X.XXX.....XX.XX..X.X.X..X.XXXX.X.XX.XXXX.X.X..X..XXX.XXX.X.X..X......XX..XX.XXXX..XXXXXX..X.. .XXX....X....X.XX.XX.XXX...X.XXXX.XXX..XX.....XX..X.X..XXX.X...XX.X.......XXX....X.X...X.....XX..X. .XXXXXXXXXX.X..XXX.X...X..XXX.XXX....X..XXXXXX.X.XXXX..XXX..X.XXX...X...X....X.X..X.....XXX..X...X. .....X..XXX..XXX.XX...X..XX.X..XX.X.......XXXXXXXXXX.X.X.X.XX.XX.X..X...X......X.X...XX....X.X..... .XXXXX.XXXX...XXX.....X.XXXX..XXX.XXXXX....XXX....XXX.XXX.X..X.XXXX.....XX.X.....XXXXX.X.X.XXXX..XX XX.X..XX.XXX.XXX.XXX..X...X.XXXX..X......X...XX.......XXX..X..XXXX...X.XX.XXX.X..X..X..X.X....X.X.. XX..XX.X...XXX.XX.....XXX.....XXXX.XX.XXXXXXXXX.XXX..XXXXX.X.XXX.XX.XX...X..XXX...X..X..XX.X...X.X. ..XX.....XXXXX....X..X..X.XX.XXX.X......XXX..XX..XX.XX...X.XXX.XXXXXXXXXXX..XX..X.X...X...X........ X.XXXXXX.X.....X..X.XXXX...X.X..XXX..X.XXXXX.X..X.X....XX.X.XX.X.XXXXXX..X.XXXX...X.....XXXXXXXXXXX .......X..X.XXXX...X.XX.X.XXXXXXX.X.X..X.XXXXX....XX.XX.......XX.XXXXXX.X...XX.XXX.X...XX.XX..X.X.X .XX..XXXX...X..X.XX.XX...XXX.X..XXX.XX..X.X.XXX..X..X.XXX....XXX.XX....XX.X.XXXX.....X.X.XXXXX..... X.XX.XX..XX.....XX.XX.XXX..XX......X.XXX.XX.XX.XX.XX.X......XX..XXX..XX..XX..XXX...XXX.XX..X...X..X X.XXX...X.....X..X.XX.X.XXXXXX.....XX.X..XXXXX..X...XXXX.XX....XX.X..XX..X..XXXXX...X..X.XX..XX.XXX X..XX..X.XX.XXX.XX.XX.XX.X...XX..XX...XXX.X.X.XX.....X...X.XX..X.XXXXX...X.XXXX..X..X.X...X.X....X. .X..XX.XXX.X.X.X.X.XX.X.X.......X.XX..X.X..X..XX..X....XX.XXX..X...XX....X.XXXXXXX.X...XXX.XXX..X.X ....XXX.X.X.X....X...X.....X.X.XX..X.XX..X....XX.X.X..X.X...XX.X...X..X...X....XXX.X.X...XXX...XXX. XXXX.XX.X.XXXXXXX...XXXX..X...X.X..XXX..X....X.X.XXXXXXX.X..XX.X.X.XX.X.XX.XXXX.X...X.XXX.X.XX..XX. X..XX.XXX.XXX.X.X.XX.XXXX....X.XX.X.X...X..XXXX..X.X..X.XXXX...XX...X....XX.X.........XXX.X.XX...XX .X....XXXXX..XX.XXX.X...X..X.X.X.XX.XXX.XX..XXXX..X.XXX.X...XXXX.X..X.X..XX.X.X.XX...X..XXXXXXXX.XX XX.....X.X....XX..XX.XXXX.XXXX...X.........XX....XX....X.X....XX.XX.XXXX..X..X....X.X.XX...X.X.XX.. ...X.XX.XXX.XXX.X...XXX...XXX.XXXX.X.XXX.X...X..XX....X..X...X.XXX.XXX.......XXX.XX..X..XXXXXXXXX.. ........X.X..X..XX.XXX.X.XXXXXXX.X.X.X.X..XXXXX..XXX.....X.....XX......X.XX...XX.....X...XX.XX..X.X X......XX.X...X......X..X.X.X..XX......XX..XX.......XX.X.X.X...XX..X.XXXXX.X.XXXX.X.XX...X.X.XX.XX. ..XXXXX....XX.XXX.....X.XXXXX....XX.XXX..XX......XX.XXXX.X..X.X...XX.XXX....XX..X..XXX.XXX..X..XXXX X..XXX.X..XX.....X.....XXXXXX.X....XXXX..X.XX..X.XXX....XX..XX.X.X.XXXXX...X..XXX..X.XX...X..X..X.X .XXXXX.XXXX..XX...XXX.X.X..XXX.X..X.X..X....XXXXXXX.X.X.....XXXX..X...XXXX.....X....XXXXX...X.XXX..

Output

2076

Validator 8 Validator

Input

99 XXX.X.XX.X..XXXX.XXXXXX..X...XX..XXX.X..XX.XX.XX...XXX.XXX.XXX..X.X.XXXXXX.XXXXX.XX.X..XXX....XXXX. .XX...X.XXXXX..X..X.X.XXX.X.X.X.XXXXX...XXXX....X..X...X.XX.XXX.XXXXX..XX...X..X.XX.XX.XXXX..XX.XXX .XX.XX..X.XX.X..X..XX.XXXXX.X.XXX.X..X.X......XX..X.....XX.....XXXXX..X..X..X.X.X..X.X.XXXX.X..XXXX XXXXXX.X...X.....X.X.XXXX...X.X.....XX..XXX.X..X...XXX..X..XXX.X..X.XXXX..XXX.XXXX......X.X.XXXX.X. .XXXX.XX...XXX....XX.X..X.XXX.XXX.XXXX..XXXXXX..XXXX..XX..X...X.X..X.XXXX.XXXX.X..X.X..X.XXX.X....X X..XXXXXX.X.X.X..XXXXXX..X.XX...XXX.XX.XX.XXX.XX.....X..X.XX.X.X..XXXXXXXX.X.XXX.X..XXX..XXXX..XX.X XXX.XX.XXXXX..XXX..XXXXX....X..X.X..XXXXXX.XXX.X.X.XX....XXX.X..XX.XXX..XX.XX.XXXX.X.XXXX..XX.X.XXX X.X...X.XX...X..XXX.X...XX.XX......X..XXXXXXX.X.X.X..XX...X.XX..XXX.X..XXX.XXXX.XX....X.XX.XXXX..X. .XXX.XX....X.X.XXX.XX....XXXXXX.X..XXX...XXXXXXX..X.X.XX...XX..X...XX.............X...XXXX.X..XXXX. X..XX.X..X..X.XXX.XX..X...X..X.X........X.........XX.XX...XX.....X.....X.XX.XXX.XX..XX.X..X.....X.X X..XXX.XX.X.....XX.XXX...X...XXXXXX.XXX..X.X.X...X....X.......XX.X......X..XXX.XX.XX...XX.X..X...X. X.....XX.XXXX....XXXXXX..X..XXX.XXXX.X...XX.XXX.X..X...XXXXXX.X.X...XX.XX..XX.XXX..XX.X.....XXX.XXX ..X.XX.X...XXXXXXX......X..X.X.X..XX..XXXXXXXXX.XX.X.XX........X..XXXXXX.........X.XXXXX....XXX.X.. .....XX....XXXXXXX.X....XX.X.XX..X.X.XX..X.XX..X.X..X.......XXX.X...X.X.X....X.XX...XX..XX.X..XXXX. XXXXXXXX.....XXX..X.XX..XX..X..X.X..XX.XXX.XX.XX.XXX.XX...X.X..X..XXXXXXXXX..XX...X....XXXXXXXXXXX. X...X...XXX..X..XX..X.X.X.XXXXX..X.XX....XX...XXXXX.X.XX.XXXX...X.XXX.X..XX.XX.X.XX.X..XXXX.X.XXX.. X.XXXX.X..XXXX..XX...XXXX.X.X...X....X.XX.X.X.X.X.XXXXXXXX......XXXX..X....X.X....XXX....X.XX...X.. ..X.X....XXXX...XXX.X..X.XX...XXXX.....XXX..X.XXX...X.....X.XXX...XXXX.X...X..X.X.XXX.X.X.X.XX.X..X ....XX..X......X..X.X.X..XXX.XX.......XXX.X..X..XX.X.XXXX...XX...XXX..X.X.X..X.XXX..XX.XXXXXX.X...X XX.XX.XX..X....X..X.XX.XXXXX.X..XXXXX....X...XXXXXXXXX..XX.XX.X.XXXXXX.X.X.X.X..X.....XXX..XXX..XX. XX...XXXXXX.....X..XXXXXX..XX..X...XX.X..X.X.XX.X.XX.X.X..XX..XXXXX..XXX.X..XX...X.XXX.X.X...XX..XX XX..XX.X.X.X...XXX.X...XXX.XX....XX.X...X......XX...XXXXXX....X....X..X..XXXXX.X..X..XX...XXX...X.X ......X....XXXXX.X.XX.X.XX.XX....X..X.XXX.....XX.XXXXXX...XX....XX..XXX......X..X.XX..XXX.XXXX...XX XX.XX.X.XXXX...X.XX.XXX.XX....XXXXX.X..X.XX..X...XXX.X.X...XXXX.XX.X.X......X.XXXX.X...X..X...X..X. .XX.XX..X...X.....X...XXX.XX..X...X.X..X.X.XX...X...XX.X.XX..X.XX...XXX..X......X.X.X.X..XXXXX..XX. X.XXXX.XXXXX....X.X..XX.X..X.X.XX.XX.XXXX..X.X.X.X..XX...X..XXX..X.X.X.XX.X.XXXX.XXXXXX.X..XX.XX.X. ..XX..XX.....XX...X..XXX.X..X.XX..XX...X..XX.X.XXXX..X.XX..X.XX.XX..X..XXX.XXX..X..X...XXXXXX.X..X. X...X.X.X..XX.X.X...XXX...X.X.X.X...XX.XX....XX...X..X.XXXX..XXXXX..XXX.XX.XX...XX.X.XX.XX.X.XX.X.. .XX.XX..X.XXX..X.X..X...X..XX.XX....X.XX..XXX.X...XX.XXXX.X.XXXXX...X.X.XX.XXXX.X...X.XXXXX.XXX...X XXX.XX.X...XXXX.XX..X..X.XX.XXXXXXX..XXXXXXXXXX..XXXX.X..XX..XXX.......XX.XXX.X.X.X...X..X.X....... ..X....XX..XX....XXXXXX.XX.XXX...XX.XXX..X.XX...X.X..X.XXXX.X.XXXXX.X.XXXXXX.X..X...XX......X..X.X. .XXX...XXX...X....XXX...XXXXXXXX.X....X..X.X..X..XX..XXX.X.X.......XXXXX.X.XX.X....X.XXX.XXXX...X.X .X.XX..X....X.X.XXXX.XXX.X.XXXXX.....XX..X...X.X..X..X..X....X.XXXX.X.X.X..XXX.XX.XX..XXXXX..X..... XXXXX..XXXX..X.X....X........XXX..XXX..XXX...X..........X..XXX.X.XXX.....XXXXX...X..XX.........XX.X .X.XX.XX....XXXXX.XXXX.X.XXX..XXX.X..XX..X.XXX...XX..XXX.X.XXX...XX....X.XX..XX.X.X.X..XXXX..XX.... .X.X..X.XXX....X.X..X.XX.X.X.XXXXXXXX.XXXX...XXX..X.X.X.X....XXX..XX.X...X.XXX.X.X..XXX...XX.X..... ...XXX.X........X...XX.XX.XX.X.X.XX....X..XXX.X.X.XXXX..XXXX....XXX..XX.XXX......X...XXX.XXX.X..... XX...X..XX..X...X.XXX.X.XXXX..XXXX...X.X.X.XXX..XX......XXXX.X...XX...X.XX...X.X.X..XXXX..X.XX....X XXXX...X.XX..X...X..X.XX....X.XX..X..X....XXXX.X.X....XXXX..X..X..XX.X.....XX..X.X.X.XX.X.XXX...XX. ..X.....X..X....XXXX.X.XXX.X.X..X.XXX.X..XXX..X.XXXXXXXX...XXXX........X..X.XXX..X.X.XXXX.X.....X.. .....X....X..X.....XX.X.X..XX..X.X.X.XXX.X.X.X.XX...XXXX.XXX.XX.X....X.X.X.X...X.XX...XXXX..X.XXX.. XXXXX..XX.XX....X.X.X.XXX.X..XXX...XX.....XX.XX.XXXXXXX.XX.X..XX.X.XX.X..XX.XXX...XX...XXX..XXX.... XX..XX..XX.....XXX..XXXX.XX.....X.XXX.XX.XXXXXXXXXXX...X.XXX.X..........XXXXX.X.XX.X.XXX.X.XX.X.XXX .X.X..XXX.X..X.X.XXX.X..........X.XX.X.X.........X.X.XXXXX.X..X....X.XXXXXXX..X.X........XXXX..XXXX .X.X.X..X..XX.X...XX...XXXX...XX..XX..X.XX......X.XX.XX.XX..X.....X..X..XX....XXXXX.X..X..XX.XX...X XX.XX...XXXXX..XXXX.XX....XX.X.XXXXXX....XX..XX...X..XXXXX.XX...XX..X.....X.XXXXXX..X.X.XX..X...X.X XX.X..XXX.XXXXX.X.X.X.X.XX....XX..X.XXXXX.....XXX.....X.X..XX....X.X......XX.XXX.X..X.XXXXX.XX.X..X X.X...XX...XXXX..X.XXX.X.....XXX....XXX..XXXX..XX..X.X.X..XX.X.XXX...XXX.XX.XX.X.X...X.XXX...X..X.. .X..X.X.......XXX...X...X.X....X...X.XXXX...X.XXX..X..X..X.XX.X.XX.X.X..XX.XXX.X..XX.XX.XX.X...XXX. .X.X.X.XX..X.XXXX....X..XX.X.XXXXXX..XXX....X..XXX.......XX.X.X....XX.X.......XX.XXX.........X.XX.X .X..XX...XXXX.XXX..XX...XX.XX.X..X.X.XX.X...X..X..XX...X..XXXXXXXXXXX.XX.....XX.XXX...X.X..XXXXX.XX XXXXX.......XXX.X.X..X..XXX...X..X..XX.......XX.XX...XXXXX..XXXX.XXX.X.X...X.X.X..X..X......X.XXXX. .X.X.XX....X..XX.X....X..XX..XX..X..X..XXXXX....X...X.XX..X..X....X..X.X..XX...X.X.X.XXX.XXXXX.X.X. .X...XXXX.XX..........X.....X.XX.XXX..X.XXX.XX.X.XXX.XXX.X.X.X.XXX.XX.X.XXXXXX.X..X.X.XX.X.X.XX.... ..XX..X.X.X.XX...XX.X.X..XXX.X.X...XXX.XXXXXX..XX.X..X..X....XX.X...XX....X..XX.X.X.X.....XX......X X...X.X.XXXX.XXX.XXX.XX..X..X.XXXXXXX.X.XX..XX..XX...X...XX..XXXXX.X.XXX.X.XX.X.X........XXX..X.XXX X.X.XX...X..X.XXX.X.X...X.X....XX.XX.X.X..X..X.X.X..XXXX.X.X..XXX.XXXXXX.XXXX....X....X..XXX..X.XXX .XX........X.XXX.XX.X.X.XX..XXX...XX.XX..XXXXX.X.....XXX.XX.X..X......X.XX.X.X..X..XX....XX.XXX.... .X.XXX.X....X.XXXXXXX.XX......X..X..X..X.XXXX.XX.X..X.X...X..XXX..XXX..X....X.XX.XXX...XXXXXX.XXXX. ....X...X..XX.XX.XXXX.XXX....X.X....X.X...XXX.....X..X.......XXX..X.......X.XXX..XX.X..XX..XXX...X. X..XXXXXX..X.X.XX.XXX.XXXXX....XXX..XXXXX...X...X.XXXX.XX.XX.X..X....XXX...XX....X....XX..X...X.... ...X....X.XXXXX....X..X.X.X.XX.X....XX.X....X.XX.XXXX...X....XXXXXX..XX...XXX.XX.XXX...XXX...XXXX.X .XXX.XX.XXXXX.X.X..XX.X.X...X.......X.XXXXXX...X..XXX.X..XX.XX....XXX..X...XXX..XXXX....XX.....X... ..X.....X..XX.......X...XX.XXXX.XX.XXX.XX.X...X.XX..X..X..X....X...X..XX.XX.X.X.X....XX.X...XX..X.. XX.XX.....X...X........XX....XX.XXX.X.X.XX...XXX..XXXXXXXX.XX..XX.X...X...X..XXXX.X..X.X.X.X....XX. .X.X.X....XX.....XXX.XXXX.XXXX.X.XX.X.XXXXX....XX..X...X..XX.X.X..X.X...XXX..X..X.X..XX.X.X......XX X.XX.X.....X...X...XX...XX..XXXX.XX..XX..X....XXX.XX...X.XX.X....X...X.XXXXXX...XX.XXXX.X.......X.X XXX...XX.XXX.X...XX.X..XX.XXX.XXX.X.X.....XXX.XXX..X.XXX..XXX.X..X..XX.X.XXXX..X.X..XX...X....X.... XX.XXX.XX....XXX.X.X...X.X.X.X.X..XXX.XXX.XXX.XX..XXXX.XXX.X.X...XXXXXX...XX.X....X.X...XX.X.X.XXX. X...XX......XXX.X.X....X.X..XX..X..X.X..XX....XXXXX..XXXXXXX.XXX.XX.X..X..X..XXX.XX.XXX.X...X.X.XX. .X..XXXXX...XXXXXX..XX..XXX.X...X...X.X.XXX.X...XXXXXXXX.X.X.XX.X.X.XXXX.X......X..XX.XXX..X..XX..X .X..XX.XX.X.X.XX..X..XXXX.X.XXX.X.XXX.X..X..XX.X..XX.XXXX..XX.XX.....XX..XXX..X..X.XX.XX..X.X.X.X.X .....XXXX..X.XXXXXX.X.X.XX.XX..........X..XX..XXXX.X.X.XXX.X.XX...XXXX..X..X..X...X..XX..X..XX.XX.X .....XXXXXX.XX.XXX.XXX...XX..XX...XXX...XXXXX....X...X.XX....XX......X..XX.XX..X..XX..XXXX.XXXX..XX X.XX...X.XX....XXX...X.X..XX.XX.XX.X..XXXX.XXXX..X..XX..XX..X...X.XXXX.XXX.X..X.X.XX..X.X..X.XX.X.X X.X.XX..XX.X....XXX...X..X.XXX....X.X.X.X..X..XXX.XXX.X.XX.X.XX.....X.XX..XX....X....XX....X..XXXXX ...X..X.XX....X.....XX...XX..XXX.X..XXX.X...XX.X.XXX.......XXXX.X.XXXXX..X...XXXX...XX....X.X..X..X XX..X.XX..X..XX..X.XXXXXX.X.X..X.X..XX..X..X..X.X..X.X..XX.XX.....X.X.XX.XX..XXX.X...X....X..X..X.. X..X..XX...XXX..XXXXXXX.X..XXX.....X....XX...XX....XXX.X.XX..XXXX....X.X.XX.X....XXXXXX....X..XXXX. XXXXX..XX...X..XXXXX..X..X..XXX....XXXX..XXX..XX.X.XX.X.XX...XXX...XXX..XX.XX......XXXX.XXX.XXXXXXX .X..XXX..X.XX.....XXXX..XXXXXXXX...XXXXX....XX....X.X.X.X.XXXXX.X.XXX.X.XXXX.X.X.X....XXX.XXX..XXXX ....X....XX.XXXX.....XX....X.X.X.XX...XXX.....X.......X...X.XXX.X....X.X..X..XXXXX.XX.X.X.XX...XXX. X.XXXXXXX..X....X.XXX..X.....XX.X..X.XXX...XX.XXXX.....XX..X..X..XXX.XXXX...X..XXX..XX...X.XXX.XX.. ...XXX.XXXXX..XX.X.X.XXXX...X.X..X...........X.XXXX.XXXXXX.X..X.X.X...X.XX.X.XXXX..X.XXXX.XXX.XX..X XX...XXXX...X......XXXXXX.X..XXX.X..X.XX.X..XXXX...X.XX......X...X..XXXX....X.XXXXXX..X.XX...X.XX.X X.X...XX.....XX....X.....XX...XXX...X.X...XX.XX...X.X..X.X.X.X....X...X.X..XX.XX.XXX..XX...XXXXX... .XXXX..XX.X.....X.XXX..X..XX...XX.XXX.X......X.X..X.X.XX.XX.X...XXX.....X..X.....X..XX.X..XXXX...XX X.X...XXX.X.X.XX..X.....XX.....XX.XX.X..XXX.XXX.XX.X.XXXX..XX..XXX..XX.XXX.XX.XXXXXX.XX.X.X.X.X.X.X X..X.XX....X.XXXXXX.X.X..XXXXXXX.X..XX.XX.X...X.....X.X.X.X...X.XXX..X.XXX....XXX.XXX...XXX..X..XX. XXX...XXXXXX.X.XXXXXXXXXX.XXX...XX....X.XXXXXX....X.X....X..XXXX.XXXXX...X..XXXXXX.XXXXX.XX..X.XX.X ..XX.XXXXX.XX.X....X...XXX.XX.XX.X.X.X..XX.X...XX.XXXX..X.XX...X.XX.X.XXXX..X.X..XX..XX.X.X.XXX.X.X ....XXXX.XX..XXX..XXX..XXXXXX...XXX...XXX..X.X.XXXXX.X.XXX.X.X..X..XX..X..X..X..X.XX.X...X...X.X..X ..X.....XX..X...XXXX.XXXX.XX.X.X..XXXXX...X.X....X...XXXX.X.X.XX..X.X..X..XX...XXX.X...XX.XXX...X.X X..XX..X..XXX.X.X.X.XX.XX..X..XXX..XX.XXXXX.X.X.....X.XX.XX..XXX.X.X.X.X.......X.XXX.XX.XX.....XX.X X.XX...XXXXXX.X..X.....X.X..XX.XX...XX.X..X..XX..XX.XXX.X.X..X.X.XXX...XX..XX..XXXXX.XXXX..XX..X.XX X.XX.X.XXXX.XXXXX.....XX.XX..XXXXX.X.XXX........X.X....XXXXX..XX...X.X..X..XX....XX..X..X.X.XX.XXXX ..XX..X.XX.X.X.XXXX..X..XXX.XXXX.X.....X..X.XXXX.X...XXX..XX.X.XX..X.....X.X.X.XX.X...X.X..X.X....X X...XX..X.XXXXX...XX...XXXXXXXX..X....XXX..X.XXX.....XXXX.XX...XXX..XXXX...XX.X..XX.....X.XX..XX.XX XXX.X.XXX..XX..XX.X.X..XX....XXXXXX.X..XX..X..XXX.XX.X.X.XX..X..X.XXXXXX.X...X.X...X...X......X.X..

Output

2099

Size 1 Test

Input

1 .

Output

Validator 9 Validator

Input

1 X

Output

Solution language

Solution

Stub generator input

Comments

16 Comments

5DN1L Unnamed CodinGamer

about 2 years ago

Added "write maximum number of rooks" to stub generator.

java_coffee_cup Unnamed CodinGamer

over 5 years ago

Finally got it solved. The algorithm is abstract to digest but easy to implement

Tried a pure logical deduction approach but my answers are a bit off from your answers in 99 size. Cannot validate it yet. Perhaps I need a mixture of deduction and brute-force to crack it. Hard puzzles are hard to get passed nowadays with the one-month limit. For me, It is not uncommon to spend a few months to solve one interesting but difficult puzzle.

Niako Unnamed CodinGamer

There is a nice and neat polynomial-time approach, that's why this kind of problem is interesting ;-) (as it might look like some NP-complete constraint solving problem, but it's not). Deduction+backtracking/brute-force approaches probably won't pass within the time limit. Think about different ways to see the problem and try to reduce it to something else (involving graphs).

CodinBot Unnamed CodinGamer

Hey CodinGamer! Your contribution has unfortunately not been moderated on time and will temporarily be removed from the system... But no worries! You can republish it anytime to give it another chance! :)

Is this problem too hard or something? It however involves a useful reduction to solve a certain kind of combinatorial optimization problems (and more common that it may seem). This is for instance a minimal prerequisite to solve the harder Google Code Jam 2017 qualification problem D (Fashion Show) or 2018 round 2 problem C (Costume Change).

Cr3aHal0 Unnamed CodinGamer

Do you have any lecture involving the reduction you mentioned ? I would be really interested to understand how they come to it + I guess this may be a very interesting topic to read about for algorithm culture.

Merlin2192 Unnamed CodinGamer

"must be separated by an occupied square" could be also "must be separated by one or more occupied squares"

Right. Changed it to "at least one". Thanks!

almost 6 years ago