Problem K
Polya Conjecture

By Linas at the English Wikipedia, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1869174

Thinking about solar eclipses has put Ivan in the mood to consider systems in which simple, regular behavior leads to seemingly irregular outcomes—such as simple orbital mechanics leading to seemingly irregular times and places of eclipses, or simple rules of arithmetic leading to the seemingly irregular distribution of prime numbers.

Let $\Omega (n)$ denote the total number of prime factors of an integer $n \geq 1$. That is, if $n = p_1^{\alpha _1} p_2^{\alpha _2} \cdots p_ k^{\alpha _ k}$ is the prime factorization of $n$ (where $p_1, \dots , p_ k$ are distinct primes), then $\Omega (n) = \alpha _1 + \alpha _2 + \dots + \alpha _ k$. For example, $\Omega (12) = 3$ since $12 = 2 \cdot 2 \cdot 3$. Note that $\Omega (1) = 0$.

Now let $\lambda (n) = (-1)^{\Omega (n)}$, so that $\lambda (n) = 1$ if $n$ has an even number of prime factors, and $\lambda (n) = -1$ if $n$ has an odd number of prime factors. Then define

so $L(n)$ is the difference between the number of $k$ up to $n$ with even and odd numbers of prime factors. For example, up to $n = 12$, there are five integers with an even number of prime factors (namely, $1$, $4$, $6$, $9$, and $10$), and seven with an odd number of prime factors ($2$, $3$, $5$, $7$, $8$, $11$, $12$), so $L(12) = 5 - 7 = -2$.

The Polya Conjecture stated that $L(n) \leq 0$ for all $n > 1$, that is, up to any $n$ there are always more integers with an odd number of prime factors than with an even number of prime factors. However, this conjecture turns out to be false, and was disproven in 1958, with the smallest counterexample $n = 906\, 150\, 257$ found in 1980.

Input

The input consists of a single integer $d$ ($0 \leq d \leq 1000$).

Output

Output a single integer, the smallest $n > 1$ for which $L(n) = -d$. For this range of $d$ values, it is guaranteed that the answer will be at most $10^6$.

1

3

2

8

12

176