Vadim invented a new chess piece, which he called a Rastafarian. A Rastafarian must stand in the center of a cell; it does not move across the board, but it looks in absolutely all directions. If it sees some piece, it treats it calmly, but if it cannot see some piece (the view is blocked by another piece; in this problem you may assume that each piece is a point; the view is blocked if another figure stands on the segment between two figures), then the Rastafarian can capture it. Below are examples of cases when a Rastafarian (M) captures another piece (E), because another piece (F) blocks the view:

Your task is to place exactly N Rastafarians on an N × N chessboard so that no two of them capture each other.

The only line contains an integer N — the size of the chessboard (2 ≤ N ≤ 1000).

Output N pairs of numbers x_i and y_i — the row and column of the cell where the i-th Rastafarian is placed. All cells must be pairwise distinct, and no Rastafarian can attack another Rastafarian.

It is guaranteed that a solution exists. If there are multiple solutions, output any of them.