Yêu cầu

Nhập vào một số nguyên dương ~n~ và liệt kê tất cả các phân số tối giản dạng ~\displaystyle \frac{a}{b}~ ~(1\le a,b\le n)~ theo thứ tự tăng dần.

Dữ liệu

Một dòng duy nhất gồm số nguyên dương ~n~ ~(n\le 1000)~.

Kết quả

Ghi ra các phân số tối giản dạng ~\displaystyle \frac{a}{b}~ ~(1\le a,b\le n)~ theo thứ tự tăng dần, mỗi dòng ghi tử số và mẫu số của một phân số cách nhau bởi dấu cách.

Input

4

Output

1 4
1 3
1 2
2 3
3 4
1 1
4 3
3 2
2 1
3 1
4 1

Giải thích:

Phân số được liệt kê ~\displaystyle \frac{1}{4} \lt \frac{1}{3} \lt ... \lt \frac{4}{1}~