Cow Pals

Interview

Time limit1sMemory limit128 MB

Summary

Find the smallest number n >= S whose proper-divisor sum m satisfies n as the proper-divisor sum of m, then print n and m.

Level: Medium4 of 10
Topics: Number theory, Brute force, Math, Implementation
Solved: No attempts yet

Problem

Bessie and all the other cows wear an RFID serial-number tag in their ear so that Farmer John can tally them mechanically.

A cow's cowpal (pal) is a cow whose serial number equals the sum of the proper divisors (the divisors of the number excluding the number itself) of that cow's own serial number. Some cows have no pal, because no cow's serial number matches their divisor sum.

Two cows are superpals when their serial numbers make each of them a pal of the other — that is, each one's serial number is the proper-divisor sum of the other's. Cows that would be a superpal of themselves are shunned; do not consider them.

Given an integer $S$ ( $6 \le S \le 18{,}000$ ), find the first cow whose serial number is at least $S$ and that has a superpal.

For example, the proper divisors of $220$ are $1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110$ , and their sum is $284$ . Likewise, the proper divisors of $284$ are $1, 2, 4, 71, 142$ , and their sum is $220$ . So $220$ and $284$ are superpals of each other.

Input

Line 1: a single integer $S$ .

Output

Line 1: two space-separated integers — the serial number of the first superpal whose serial number is at least $S$ , followed by the serial number of her pal.

Examples1

Example 1
Input
```
206
```
Expected output
```
220 284
```