Cho một số tự nhiên \(N\). Hãy liệt kê tất cả cặp số \((i,j)\) sao cho \(1 \leq i,j \leq N\)

Input

• Một số \(N (1 \leq N \leq 1000)\) duy nhất

Output

• Liệt kê các cặp số theo thứ tự tăng dần của số thứ nhất. Nếu số thứ nhất bằng nhau, hãy xếp theo số thứ hai.

Example

3

1 1
1 2
1 3 
2 1
2 2 
2 3 
3 1
3 2 
3 3