Uolevi ja Maija pelaavat laivanupotusta. Jotta peli ei olisi tylsä, he muuttivat kuitenkin hieman sääntöjä.

Pelissä on vain yksi laiva, jonka pituus on 4 ruutua. Maija sijoittaa sen ensin salaiseen kohtaan ruudukolla pysty- tai vaakasuuntaisesti.

Tämän jälkeen Uolevi yrittää etsiä laivan. Joka vuorolla Uolevi tutkii yhden ruudun ruudukolla. Jos ruutu on osa Maijan laivaa, peli päättyy.

Pelialueen koko on n \times n ruutua. Tehtäväsi on etsiä pienin määrä ruutuja, jotka Uolevin riittää tutkia, jotta Maijan laiva löytyy varmasti.

Syöte

Syötteenä on kokonaisluku n, joka määrittää ruudukon koon.

Tuloste

Ohjelmasi tulee tulostaa n \times n -ruudukko. Jokainen ruudukon merkki on . tai *. Jos merkki on *, Uolevi tutkii sen ruudun.

Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Esimerkki

Syöte:

5

Tuloste:

..*..
*...*
...*.
.*...
..*..

Osatehtävä 1 (24 pistettä)

• 1 \le n \le 10

Osatehtävä 2 (49 pistettä)

• 1 \le n \le 100

Osatehtävä 3 (27 pistettä)

• 1 \le n \le 1000