RoAlgo Contest #11 - Back to School 2024 | antidivizibil

Task

School starts on Monday, and as a diligent student, you want to impress your classmates with the things you've learned during the vacation by being active on RoAlgo, to convince them to be active on the server as well. Today, after a successful round on Olympforces, you want to show your classmates one of the problems that appeared there.

You are given a number $n$, and the only thing you need to do is to display the smallest number with $n$ digits that has the property that none of its prefixes is a divisor of the displayed number. We don't consider the entire number as a prefix.

For example, if $n = 3$, $x = 321$ does not satisfy the required property because $3$ is a divisor of $321$. Also, $29$ is not a valid answer because it has $2$ digits, not $3$ as required by the problem.

A valid example is $951$, as $951$ is not a multiple of either $9$ or $95$, however it is not the smallest such $3$-digit number.

Our hero solved the problem in 2 minutes; now it's your turn to show that he’s not the only one who can do it.

Input data

The first line will contain the integer $n$, the length of the required number.

Output data

The first line will contain a single integer, the required result.

Constraints and clarifications

• $2 \leq n \leq 100$;
• For tests worth $30$ points, $n \leq 9$.
• For tests worth an additional $20$ points, $n \leq 18$.

Example

stdin

2

stdout

21