Fake Prime

Jigui met a problem that is only solvable after deciding whether a number around ten billion is prime. He wrote code that divides by every integer from 2 to $\sqrt{N}$, but it produced no result after an hour. A search turned up Fermat's little theorem.

For a prime $p$ and every natural number $a$ with $\gcd(a, p) = 1$, $a^{p-1} \equiv 1 \pmod p$.

Jigui used it backwards and wrote code that reports $n$ as prime when $2^{n-1} \equiv 1 \pmod n$. That code classified 561 as prime. Jigui did not give up, widened the set of bases, and settled on the following test.

Given a natural number $n$, if every integer $a$ with $2 \le a \le 500$ satisfies $a^{n-1} \equiv 1 \pmod n$, report $n$ as prime. If even one of them fails, report $n$ as composite.

Jigui checked every number up to one million by computer, submitted the answer with confidence, and was wrong again. When $n > 500$ a prime is always reported as prime, so the only way this test errs is by reporting a composite number as prime. Call such an $n$ a counterexample.

Show Jigui a counterexample. Given an integer $L$, find the smallest counterexample greater than $L$ and the smallest prime factor of that counterexample.

The first line contains an integer $L$. ($500 \le L \le 10^{12}$)

On the first line, print the smallest counterexample $n$ greater than $L$ and the smallest prime factor $m$ of $n$, separated by a space. The answer $n$ is always at most $10^{15}$, and $m$ satisfies $1 < m < n$.