Các loại số

Bối cảnh

Gọi s(x) là tổng các ước dương của x, không kể chính x.

• Hai số a < b được gọi là bạn bè nếu s(a) = b và s(b) = a.
• Số x được gọi là hoàn hảo nếu s(x) = x.

Yêu cầu

Cho số nguyên dương N. Hãy tìm các số hoàn hảo không vượt quá N và các cặp số bạn bè (a, b) có b ≤ N.

Input

Một dòng chứa số nguyên dương N.

Output

• Dòng đầu in số lượng số hoàn hảo, sau đó là các số hoàn hảo tìm được theo thứ tự tăng dần, cách nhau bởi dấu cách.
• Dòng thứ hai in số lượng cặp số bạn bè.
• Với mỗi cặp, in a b trên một dòng riêng. Các cặp được in theo thứ tự tăng dần của a.

Ràng buộc

1 ≤ N ≤ 3 × 10^6.

Ví dụ 1

Input

1000

Output

3 6 28 496
1
220 284

Ví dụ 2

Input

300

Output

2 6 28
1
220 284