Cho số nguyên dương $N$. Liệt kê các cặp số bạn bè trong phạm vi từ 1 đến $N$.

a và b được gọi là cặp số bạn bè nếu tổng các ước của a bằng b và ngược lại. Trong trường hợp bài này, Khi tính tổng các ước của một số thì không tính chính số đó.

Input

Gồm $1$ dòng chứa số nguyên dương $N$ $(7\le N\le {10}^6)$.

Output

Ghi ra các cặp số bạn bè từ 1 đến N, mỗi cặp trên một dòng, số nhỏ hơn viết trước.

Ví dụ

Input

300

Output

220 284

Nguồn