Do'st sonlar

Ikki xil natural son $a < b$ do'st sonlar deyiladi, agar $a$ ning o'zidan boshqa bo'luvchilari yig'indisi $b$ ga, $b$ niki esa $a$ ga teng bo'lsa. Masalan, $220$ va $284$: $1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284$, $1 + 2 + 4 + 71 + 142 = 220$.

Natural son $n$ berilgan. Ikkalasi ham $n$ dan oshmaydigan barcha do'st sonlar juftlarini toping.

Bitta butun son $n$ ($1 \le n \le 2 \cdot 10^4$).

Har bir juft alohida qatorda: $a$ va $b$ ($a < b$), $a$ ning o'sish tartibida. Juft bo'lmasa — 0.

Bo'luvchilar yig'indisini hisoblaydigan ichki siklni alohida funksiya qilib yozish qulay: $b = s(a)$ ni toping va $a < b \le n$ hamda $s(b) = a$ ekanini tekshiring. Bo'luvchilarni $x$ gacha emas, $\sqrt{x}$ gacha tekshirish yetarli: $d$ bo'luvchi bo'lsa, $x / d$ ham bo'luvchi. Shart d * d <= x ko'rinishida yoziladi.