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