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, ~2\,120~ is special, because ~2\,120^2 = 4\,494\,400~ and the square contains only (and all) of ~0,4,9~. ~97~ is also special: ~97^2 = 9\,409~. ~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, 2\,120, 3\,148, 7\,000, 9\,700, 9\,970, 9\,997, 20\,102, 21\,200, 31\,480, 70\,000, 97\,000, \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