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$