Constellations
Statement
Beginner astrophotographer Oleg took a photo of the night sky. Now he wants to find a number of constellations in it. This photo is [[h]] pixels in height and [[w]] pixels in width and each pixel is either a star ({{*}}) or an empty region ({{.}}). A star can be described by its coordinates {{(x, y)}} in the photo. He found following algorithm to identify constellations:
<<0)>> Initially, each star is considered as a separate constellation
<<1)>> Choose two stars in different constellations. Let {{(x1, y1)}} and {{(x2, y2)}} be coordinates of those stars.
<<2)>> If the rectilinear distance between stars is under given threshold [[t]], i.e. {{|x1 - x2|+|y1 - y2|≤ t}}, then merge corresponding constellations.
<<3)>> Repeat steps #1-2 until no merging occurs
Oleg asks you to implement above algorithm and count constellations in the photo.
Input description
<<Line 1:>> Three space-separated integers [[h]] (height of the photo), [[w]] (width of the photo), [[t]] (distance threshold)
<<Next [[h]] lines:>> String representing a row of the photo. It consists of characters {{.}} (empty region) and {{*}} (star)
Output description
Print a number of constellations in the photo
Constraints
1 ≤ [[h]], [[w]] < 100
1 ≤ [[t]] < 200
Number of stars is guaranteed to be less than or equal to 256.
Game modes
Test cases
Simple Test
Input
4 5 1
**...
*....
....*
...**
Output
2
Simple Validator
Input
4 3 1
*.*
*.*
*.*
*.*
Output
2
No stars Test
Input
3 3 3
...
...
...
Output
0
No stars Validator
Input
4 4 8
....
....
....
....
Output
0
One pix photo Test
Input
1 1 1
*
Output
1
One pix photo Validator
Input
1 1 1
.
Output
0
One row Test
Input
1 5 5
*.*.*
Output
1
One row Validator
Input
1 5 1
**.**
Output
2
One column Test
Input
5 1 2
*
.
.
.
*
Output
2
One column Validator
Input
5 1 4
*
.
.
.
*
Output
1
Sky full of stars Test
Input
16 16 1
****************
****************
****************
****************
****************
****************
****************
****************
****************
****************
****************
****************
****************
****************
****************
****************
Output
1
Sky full of stars Validator
Input
16 15 1
***************
***************
***************
***************
***************
***************
***************
***************
***************
***************
***************
***************
***************
***************
***************
***************
Output
1
Chessboard Test
Input
22 22 1
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
Output
242
Chessboard Validator
Input
22 22 1
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
.*.*.*.*.*.*.*.*.*.*.*
*.*.*.*.*.*.*.*.*.*.*.
Output
242
Diagonal Test
Input
99 99 196
*..................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
...................................................................................................
..................................................................................................*
Output
1
Diagonal Validator
Input
98 98 194
*.................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
..................................................................................................
.................................................................................................*
Output
1
Big random #1 Test
Input
99 90 7
.......................*........*.........................................................
.......................*...........*......................................................
.........................*...............*..*.............................*........*......
......................................................................*..............*....
*.............................*.............*.............................................
................*.....*................................................*..................
.....................................*.........*...*......................................
................................................................*........*................
.........................*........*...................*.................*.................
................*..................................................*......................
..........................................................*...............................
..*........................................*.......*......................................
........................*.........................*.....*.................................
............................................*.............................................
......................................................*............*......................
..*..............*......................*..........................*......................
.....................................*....................................................
...................*...*.....*............................................................
......................*.......................................*.............*.............
..........*..........................*..............................................*.....
...................................*........................*........................*..*.
..........................................................................................
............*...............................*....................................*........
.........................................*................................................
.....*.........................*..........................*..........*.....**.............
..........................................................................................
..........................................................*...............................
...............*..........................................................................
............*....*......................................*........................*........
...*...*...........................*.........................................*....**......
..................................................................................*.......
.......................................*...........................*...................*..
.......................*..............*................**.................................
...................................................*......................................
.................*..........*..............*..............................................
........................................................*.....*......................**...
..........*......*..................*......................*....*........*................
..................*....................................*..................................
....................*.*..........*........................................................
...........................*........*.....................................................
..............................*..*.*........*.............................................
.......................................................................*......*...........
.....................................................*.............................*......
...........*...*...................................*.......................*..............
.................................*.................................*......................
..........................................................................................
...............................*...................*......................................
............................................*.*...............*..*.*......................
.......*............................*..................*.........................*........
.........................................................*...............................*
..........................................................*..............................*
............*.........*...*...........*...................................................
.*................................*.......................................................
........................*............................................*.......*............
..............................................................*................*.*..*.....
....................*...............*.........................*...........................
....................*..............................................*......................
..........................................................................................
............................*..............*..............................................
............................................................*.................*...........
........................*................*.........*..................................*...
..........*...*............................................*.....*........................
................................................................*.........................
.................*..........*..........................*..................................
*.....................*.....**...............................*...........*................
.............................................*......................*.....................
..................................*..................*....................................
..............................................................................*...........
..........................................................................................
.....................*......................*..*..........................................
................................*..*..............................*.......................
...........................................*...................................**.........
..............*.........................*.......................*.........................
.....................................*.......................*............................
..................................*...............................*......................*
.................................*...................*.......*...........*........*.......
........................................................*............*....................
.................*..*.....................................................................
..........................................................................................
..................................................................................*.....*.
................*........................................................................*
............................................................................*......*.*...*
......*..*..................................*............................*...........*....
.*...........................................................*................*...........
......................*..........................................*........................
............*.............................................................................
........*....................................*...*........*..*............*...............
......*...............................*.................................*.................
..............................................................*...........................
................................................................*.................*.......
..........................................................................................
.....................*...........................................................*........
...............................................*.............*.....*......................
.................................*.....................*..............................*...
............................................*...................*...............*.........
...........................*.............*..............*.................................
..................................................*.................*.....................
.......*.................................................*................................
..........................................................................................
Output
32
Big random #1 Validator
Input
90 99 8
.....*.*...........................................................................................
............*....*.........*..............................*...............*.....**...............*.
..*...................................................................*...*........................
*.........................*.........................*...............................*..............
.............................*....*.....*..................................*..............*........
..................................................*..............*.................................
...........................*.......................................................................
...................*...*...................................*.......................................
..................*..........*.................................................*...................
..................*....................................................................*.......*..*
.............................*..*.......................................................*..........
.......................*...........................................................*...............
............................................*.....................*................................
...................................................................................................
......................................................*...........*.*..............................
*.......................................................*...........*..............................
.........*............................................................*............................
...*...................................................................*.............*.............
...............................................................................*.........*.........
.....................**............................................................................
........*.............................................*......................................*.....
...*...............................*...........................................*......*............
.....*........................................................................*....................
........................*................*......................................*.........*........
...................*..........*........................................*...........................
.*.......*.......................................*.................................................
.....................................................................*.............................
....................*.......*..........................................................*...........
.........*..............*..........................................................................
....................*.*............................................................................
.......*.....................*............................................*........................
........................................*.......*......................................*...........
.......*...........................................................................*...............
............................*......................................................................
......*............................................*...............................................
................................*...........................*..........*...........................
.*....*...*................................*........*........*.....*................*..........*...
...................................................*..................*.......*..............*.....
.............................*..................................................*..................
..................*................................................................................
.................................................................*..........*.*....................
..................................*........*.................*.....*...............................
..............................................................................................*....
.........*..........................**.......................................................*.....
.......*..*.........................................*..............................................
......*.......................................................................*..................*.
.............................................*.*................................*..................
.........*.............................................*...........*......*........................
..............*.*.............*.......*..........................*.............*...................
........*.........................*................................................................
.................................................*.................................................
.............................................*..........................*..............*...........
............................................*..............................*.......................
.....................*........................................................*....................
.................*.........*...*...............*.......*...........................................
.....*............................*............*...................................................
.............................*........................*............*.................**....*.....*.
..........................................................................*........................
................................................................................*..................
............................*......................................................................
...................................................................................................
...................................*......................................*........................
................................................*.........*..................*..............*......
...................................................................................................
.....................................................................................*....*........
.......................................................................*...........................
.........*.........................................................................................
......*....................................*......................*...............*.........*......
........*....................................*......................*................*.............
.......*...................................*........*..............................................
*...................................................................*....*.......*.................
........................**.........................................................................
..................................*................*................................*..............
..........................................*........................................................
......................*............................................................................
..*................................*.....*..............*..........................................
..............................................................*....................................
...*.........*.......................................*...*...................*.....................
.*.........*............................*..........................................................
...................................*..*.....*....................*...........*.....................
..........*......................................................................*.................
....*.....................................*..*.......................................*.......*.....
..................*.....................................*...............................*.........*
..............*...........................*........*.....*.........................................
...............................................................*...................................
..................................*..............*............*....*...............................
...................................................................................................
...........................**................................................................*.....
.....................................................................*............................*
......*..................................*..............*...........*.....*......*............*....
Output
15
Big random #2 Test
Input
99 99 4
.........................................................................*.........................
..................................*.........*......*...............................................
.........................*........*...........*..*...................*.............*...............
........*.....................*.................*..................................................
......................................................................................*............
.....*............*........................................*.......................................
........................*...............................*................*.........................
............................................*..........*...........................................
.........................................*.....................................................*...
.........................................................*...**..*.................................
......................................*............................*...............................
......*............................................................................................
....*............*..................*...................*.....................*................*...
..................................................................*............................*...
............*.................................................................*....................
...................................................................................*....*..........
...................................................................................................
.....................................................*.............*.....*..*......................
.......................................................................*........................*..
......*......*.....................................................................................
........*...................................................*............................*.........
.......................**.*...*.....................*..................*...........................
.......................................................*...........................................
....*..............................................................................................
...................................................................................................
......*.................................................................*..........................
................................*............*.........*........*..................................
....*.............................................................................................*
...................................................*...............................................
...............*..............*.....................................**...........................*.
.......*.......*...................................................................................
...................................................................*.................*.............
*.........................*..................*..........*..........................................
*.................................*...*...*...........................*...................*........
...............................................................*.....*.............................
.*.........................................................................................*...*...
.............................................................................*......*..............
..............................*.......................................*............................
.............................*.......................................................*............*
..................*....................*................*.....................*....................
...*...*......................................................*....................................
........................*...................................*.......*.*............................
.............*...................................................*.....*...........................
...*.........................................*..................*..................................
..................................**.................*.............................................
*.....................................*...........*................................................
.....*.....*......................*................................................................
..................................................*................................................
...................................................*..............*................................
.*........*..........................*.....................................................*.......
...................................................*....*..........................................
.................*.............................*...................................................
......*.................*............*..................*..*.....................*.................
................................................................................................*..
........................................................*....................................*.....
........................................................*......................................*...
...................*...........................................................*.....*.....*.......
...............................................................................................*...
.............................................................*......*..............................
...........................*......*..........*.....................................................
........*.................................................*..............*.....*........*.......*..
..........................................................*.....................................*..
..*....................*.......*....................**.............................................
.................................................*.................................................
...................................................................................................
.*......................................*..........................................................
................................................................*.................................*
......................................................................*............................
........*.............*........................................................*...............*...
.......................*...........................................................*...............
...*.......*.................................................................*.*...................
........*...................*................*....*...............................*................
...................*.............*.................................................................
...................................................................................................
..........................................................................*........................
.............................................................*.....................................
.....*...........................................................*.................................
............................*......................................................................
.....................................*.............................*.*.............................
.....................*......*..............................................................*.......
.........................*.....*................................................*.**...............
........*..........................................................................................
.................*.....................................*...........................................
..............*.*......*...........................................................................
...................................*....................*..........................................
..............*............................................*...............*.......................
...............................................................*................................*..
........................................*..........................................................
...............................*.................*.................................................
...........................*..........*.........*..................................................
................................................*.*...............................*................
...................................................................................................
................*.............*..............................*..*......*...........................
.......................*..........................................*.........**...........*.........
...............................*...*............*..................................................
........................*...............................................................*..........
.....................*...................*....................................................*....
.................*.................................................................................
......*..............*........................................................................*....
Output
143
Big random #2 Validator
Input
99 99 3
...........................................................................................*..*....
.................................................................*........................*....*...
...*.................................*..................*...................................*......
.*..............*........*..*..*...................................................................
..................................*.................*..............................................
........................................................*..........................................
.......................................*...........................................................
...................................................................................................
...................................................................................*...............
................................................*................*.................................
....*..................................................................*...........................
.....................*.................................................*...........................
..................................................................................................*
...................................................................................................
...............*..........................................*........................................
..............*..........*.........*.*......*.........*............................................
.......................................................*...........................................
...................*...............................**......................*.......................
............................................*...............................*......................
.........................*...............*.........................................................
..................................................................*.........................*......
..............................................................*................*...................
...............................................*.................*..*................*.............
......*.........*.......................................................*..........................
...........*.......*.................................*..........*..................................
............*........*...*....................*................*...................................
...........................*..............................*........................................
............................*.....*..........*................*....................................
......................................................................*................*...........
...*.......................................................*...............................*.......
........................................................................................*..........
........*..............*..............................................*.*..........................
.................................*.......................*.........................................
.......................*...*.........................*........**......*.................*..........
...........*........................*.....................................*................*.....*.
........................................*..........................................................
......................*.....*....................................*.................................
.....................................................................*............*..*.............
.....................................................................*.............................
..................*........................*.......................................................
......................................................................*.*......................*...
....*...................................................*..........................................
..................................*....*.............................................*.............
..*.................................................................*...*.*........................
...................*...................................*....*..................................*...
.........................................................................*......................*..
...................*.............*......................................................*..........
............................*......................*.......................*......................*
..............................*....................................................................
............*.................*......................*.............................................
..*...................................*............................................................
....................*...................................*..........................................
...*....*..........................................................................*....*..........
............................................*............*...*.......................*.............
......................................................*..............*.................*..*........
.........*...........................................................................*.....*.......
..............................................*.............................*......................
...................................................................................................
*......*.......................................................................................*...
.................................................*.............................................*...
......................*............................................................................
...........................*.............................*..............................*..*.......
.............................*..................*..*...............................................
......................................*............................................................
......................................................................*...................*........
.............................*...................*......................*..........................
..................................................*....*.....................................*.....
.................*..................................*..............................................
*...................*........................................*.....................................
........................................................................**.........................
..................*................................................................................
..*............................................................................*...................
..................................*................*...............................................
..........................................................*..................................*.....
...................................................................................................
...............*..........................................*..................*.....................
..................................*..............*....................................*............
............................................*...................................*..................
..*................................................................................................
.*....................................*............................................................
...............................*................................*.....................*.*......*...
.....................................*.............................................................
....*......................*.......................................................................
......*....*.......................................................................................
..................................................*................*...............................
...*.......................*............*...*...........*................*.....*...................
.................*.........................*........*...................................*..........
....................................*............................................................*.
.......................*.........................................*..........................*......
..........*...................................................*...........*....*...................
.............................................................................................*...*.
.................*.....*.............*.......*..................................................*.*
.....................................................................*.........*...................
..................................................*.................*................*...........*.
........................................*........*..............................*..................
......*........................................................*...................................
........................................................................*..........................
..................................................................*................................
.....................................................................................**.........*..
Output
178
Big random #3 Test
Input
97 98 10
..............................*...........................*...................*........*..........
............................................*..*...............*..................................
...*...............*...*..........................................................................
......*...........................................................................................
...........................................................*......................................
.........*...............................................................................*........
..................................................................*................*..............
...............................*..................................................................
................................*.......**........................................................
....*.......................................*............................*......*.................
.................................................................................*................
.........*..............*...................*.....................................................
...........................................**................................*....................
......................*...........................................................................
.........*....................*.....*.............................................................
...................*.......*....................................................*................*
.................*..*..................................*...............*..........................
.....*.......*......*...........................................*.................................
............................................................*..*..................................
......................*............*...........*.......................*................*.........
...................*...............................................*.......*......................
..................................................................................................
.*.....*.......................................*.............*....................................
..................................................................................................
..............................................................................*...................
...................................................*...........*....................*.*...........
.........*.......................................................................*.......*........
..................*.................*.............................................*...............
...................................................................................*..............
...........................*.........................................*................*...........
...................................................*....................................*.........
................................*...............*......*..........................................
...........................................................................................*......
.......*.....................*...................................................................*
..........*.........................................*.............................................
..................................................................................................
......................................................................*...........................
...........................*...........................................*..........................
..............................................................*......*...........................*
..................................................................*...............................
......*.............*.....................................................*.................*.....
....................*.......................*...............................................*.....
*..................*..............................................*.................*..*..........
.............*....................................................................................
................................................*.................................................
...........................................*...............*.....*................................
...........................*.................................*..................................*.
.......................................................................................*..........
.....*............................*...................................*...........................
.....*............................*.................................................*.............
..................................................................................................
........*........*.....*........**........*..................*..............*...*.................
.........*........*................................................................*..............
...............................................................*.................................*
................................*................*................................................
.................................................................*.....*..........................
..................................................................................................
*.............................................*.........*....*................*......**..........*
........*......................**...*.............................................................
...........................*.......*............................................................*.
.....................................................*............................................
.................................*.............................................................*..
................................................................*............*........*...........
..................................................................................................
................*........*....*..................*..........*.....................................
......................................*............................*....*.........................
.................*.............*........**.......................*..*..................**.........
...........................*......................................................................
*.................................................................................................
........*...........................................................*.............................
........*......................................................*..................................
.............................*....................*...............................................
...................................................*..............................................
.......*.*..............*...............................................................*.........
................................................................*.......................*.........
.................................................................................*................
......................................................*.........*........................*........
..........*.............................................*............*....*.......................
....................................................................................*........*....
........................*..........**.......*.*...........*......*................................
................*............................................................................*....
.....*.............*..................*.............................*.............................
....*.....................................................*............*......*..*................
................*........*.........*..........................*.........*.........................
....*.....................*.......................................................................
..................................................*...................................*....*......
..*.................................................**............................................
..................................................................*...............................
..........................................*................................................*......
..................................................................................................
..........................................................................................*.......
..................................................................................................
..................*...................*........................*..................*...*..........*
.....................................*.................*..........*...............................
.......................*.......*..............................................*.....*.............
*................................................................*................................
*....*.............................................................*......**......................
Output
4
Big random #3 Validator
Input
97 96 11
...........................................................................*....................
................................................................................................
.............................*............................................*.....................
..*.............................................................................................
...............................................................*................................
..........................................................................................*.*...
................................................................................................
...*....*.........................*................*............................................
........................................................................*.......................
*..........................................................*...............*....................
.....................................*.*........................................................
........*...................*................................*...................*..............
.....*.............................*...............................*............................
.................................*...........*........*....*..............*.....................
....................................*....*.............*.............*..........................
..........*......*.....*........................................................*...............
..............................................*...............*.................................
......*...................................................................................*.**..
.................................*............................*.........................*.......
.........................*....................................................*.................
...........................*.............*..................................*...................
..................................................*.............................................
................*.......*................*......................................................
................................................................*.................*.............
................*...*...........................................*.....*...*.............*.......
..........................**.........................................*................*.........
.....................................................*...................................*...*..
......*.............*...*...............*...................................................*...
................................*.....................*.......**.........*......................
.........................................*......................................................
............................*................................................*.............*....
....................*...................*.......................................................
.............................*.....................*.........................*..................
........*........*..............................................................*.....*.........
...............................................*........................*.......................
................................*.*...................................*.........................
..................................*...........*.................................................
*.......................*............*...............................................*..........
..........................................*.....................................................
............*...........*..............................................................*........
..........*.....................................................................................
.................................*..............................................................
...........................................*...............................................*....
............*...................................................................................
...*......*.....................................................................................
...................................*.....*.....................*................*...............
................................*..........*............*.......................................
......*.........................................................................................
..........................................*.......................................*.............
...........*......*........................*...............................*.........*..........
......................................................................*.............*...........
........................*...*......*..................................*.........................
.*......*...........................*...........................................................
................................................................................................
.......*................................*....*...............................*..................
..............................**............*....*........*......*..............................
..............................................*................................*................
....................................*.........................*................*.......*........
...........................................................*....................................
......*.....*...................................................................................
.............................................................................................*..
..............*.*...............................................................................
....*.......*..............*................*............................................*......
.........................*...............*............*...*......................**.............
...............................*....................*...........................................
.......................................*.......................*................................
.......................................................................*........................
..........................*..........*..........................................................
................................................................................................
....................*....*.*................................................*...................
............................................................................*...................
..................*...*.........*...............................................................
......................................*...........................................*.............
.........*.....*..............................................*...............................*.
.........*.............*.................................................*......................
..........................................................................*..........*...*......
.......................*..............................*..................*......................
................................*..*..................*.....*..............................*....
.............*.....*....................................*.......................................
.....................................................................*..........................
...*...................................*...........................................*............
................................................*............................*..................
..............................................................................................*.
..........*................*.......................*............................................
........................*.*............*.....................*..................................
........................................................................................*.*.....
......................................*............**..............................*.*..........
........................................................*................................*...*.*
*.....................................*..............................................*....**....
..................................................................*..*..........................
...............*................................................................................
.........................................................................*.......*..............
................................................................................................
..........................................................................*..*...........*......
................*...*..*........................................................................
..............*................................................................*................
......*.........................*..............*................................................
Output
3
Solution language
Solution
Stub generator input