Knight’s Tour (नाइट्स टूर)

आपको एक खाली n x n चेसबोर्ड दिया गया है, और एक नाइट (अश्व) चेसबोर्ड के पहले खाने पर रखा गया है। नाइट शतरंज के नियमों के अनुसार चलता है और उसे बोर्ड के प्रत्येक खाने पर ठीक एक बार जाना होगा। आपका कार्य यह बताना है कि नाइट किस क्रम में प्रत्येक खाने पर जाएगा।

इनपुट

इनपुट में एक ही पूर्णांक n (5 ≤ n ≤ 30) दिया जाता है, जो चेसबोर्ड का आकार दर्शाता है।

आउटपुट

आपको n पंक्तियाँ प्रिंट करनी हैं, जिनमें प्रत्येक पंक्ति में n स्थानों से अलग-अलग की गई संख्याएँ होंगी। ये संख्याएँ उस क्रम को दर्शाती हैं जिसमें नाइट उन खानों पर गया। इन संख्याओं का दायरा 0 से तक होना चाहिए, जिससे यात्रा का क्रम पता चलता है। कार्यक्रम किसी भी मान्य हल को प्रदर्शित कर सकता है।

उदाहरण