Ratsun reitit

• Time limit: 1.00 s
• Memory limit: 512 MB

Ratsu lähtee liikkeelle $n \times n$ -kokoisen shakkilaudan vasemmasta yläkulmasta. Ilmoita jokaiselle laudan ruudulle pienin määrä siirtoja, joilla ratsu voi päästä kyseiseen ruutuun lähtöruudustaan.

Ratsu liikkuu yhdellä siirrolla askeleen vaakasuunnassa ja kaksi askelta pystysuunnassa tai askeleen pystysuunnassa ja kaksi askelta vaakasuunnassa.

Syöte

Syötteen ainoalla rivillä on kokonaisluku $n$.

Tuloste

Tulosta $n$ riviä, joista jokaisella on $n$ lukua: pienin siirtojen määrä kuhunkin ruutuun.

Esimerkki 1

Syöte:
4

Tuloste:
0 3 2 5
3 4 1 2
2 1 4 3
5 2 3 2

Esimerkki 2

Syöte:
5

Tuloste:
0 3 2 3 2
3 4 1 2 3
2 1 4 3 2
3 2 3 2 3
2 3 2 3 4

Osatehtävä 1 (27 pistettä)

• $4 \le n \le 10$
  

Osatehtävä 2 (31 pistettä)

• $4 \le n \le 50$
  

Osatehtävä 3 (42 pistettä)

• $4 \le n \le 100$