Zinium is a miracle of our world - and probably of all the worlds. Found at the close of the XIX-th century during archeological dig on the territory of modern Albania, Zinium belonged to Caesar himself and was lost in his last campaign.

The artifact is a chessboard of N*N cells in size. A cell in its left-bottom corner has coordinates (1, 1) and a cell in its right-top corner has coordinates (N, N). The legend says if one could place N queens onto the board in such a way, that none of them attacks the other, released energy of Zinium will change the world beyond recognition. Rivers will turn back, the sky will fall onto the earth, people will learn to call things by their proper names... Petr the Gorgeous himself will probably participate in the Fourth Challenge of Timus Top Coders... Or will not. So, it is high time to check it.

The only line contains the integer number N (4 ≤ N ≤ 100000).

For each queen you should output the coordinates of its cell on a separate line. The coordinates should be separated by single spaces. The queens may be listed in any order. If the problem has several solutions, you should output any of them.

Two queens attack themselves, if they are placed in the cells positioned on the same horizontal, vertical or diagonal line.