2009 Bulgarian Olympiad in Informatics

Consider the positive integers whose squares contain only (and all) the digits $0,4,9$. Let's call them "special". For example, $2120$ is special, because $2{120}^2=4494400$ and the square contains only (and all) of $0,4,9$. $97$ is also special: ${97}^2=9409$. $13$ and $7$ are not special - ${13}^2=169$ ($1$ and $6$ aren't allowed) and $7^2=49$ (there's no $0$).

Consider the sequence of special numbers, in order:

$${\displaystyle \{70,97,700,970,997,2120,3148,7000,9700,9970,9997,20102,21200,31480,70000,97000,\dots \}}$$

Write a program to find the $N^{\text{th}}$ number in this sequence.

Input Specification

The positive integer $N\le 250$, on a single line.

Output Specification

The $N^{\text{th}}$ number in the special sequence (starting from $1$).

Sample Input

12

Sample Output

20102