Atın yolu

n \times n ölçülü şahmat taxtası verilib. At boş taxtanın ilk sətrinin birinci sütununda (yuxarı sol küncündə) yerləşdirilib. Şahmat atının hərəkət qaydalarına uyğun olaraq, taxtanın hər bir xanəsini məhz bir dəfə ziyarət edin.

\InputFileŞahmat taxtasının ölçüsü $n$ (1 \leq n \leq 8).

\OutputFileAtın gedişlərinin ardıcıllığına əsasən taxtanın vəziyyətini çap edin. Əgər məsələnin həlli yoxdursa, "Solution does not exist" yazın.