### 2009 Bulgarian Olympiad in Informatics

## Task 5: Special Sequence

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 2120^{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:

{70, 97, 700, 970, 997, 2120, 3148, 7000, 9700, 9970, 9997, 20102, 21200, 31480, 70000, 97000, ...}.

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

### Input

The positive integer`N`≤ 250, on a single line.

### Output

The`N`

^{th}number in the special sequence (starting from 1).

### Sample Input

12

### Sample Output

20102

All Submissions

Best Solutions

**Point Value:** 30 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 32M

**Added:** May 11, 2009

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...