Centre for Gifted Education - Hanoi university of Technology

Hãy đặt n quân hậu trên bàn cờ vua kích thước n×n sao cho không có quân hậu nào có thể "ăn" được quân hậu khác, hay nói khác đi không quân hậu nào có để di chuyển theo quy tắc cờ vua. Mầu của các quân hậu không có ý nghĩa trong bài toán này.

Như vậy, lời giải của bài toán là một cách xếp n quân hậu trên bàn cờ sao cho không có hai quân nào đứng trên cùng hàng, hoặc cùng cột hoặc cùng đường chéo.

Trường hợp n = 8:

Input

Dòng đầu tiên ghi số nguyên dương n (n <= 25)

Output

Gồm n dòng: Mỗi dòng ghi 2 số nguyên i, j là toạ độ đặt 1 quân hậu

Example

Input:
8

Output:
1 4
2 7
3 3
4 8
5 2
6 5
7 1
8 6