E. Number in Russian
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Write a program to find the smallest natural (positive integer) number so that this number, written in Russian words in the nominative case, would have a length of exactly $$$k$$$ characters excluding spaces.

Input

An integer $$$k$$$ ($$$1 \le k \le 165$$$).

Output

Output the integer found. If there is no answer, output 0.

Scoring

There are 100 tests in this problem. One point is awarded for passing each test.

Example
Input
150
Output
11488488484484
Note

The number in the example is written in Russian as: «одиннадцать триллионов четыреста восемьдесят восемь миллиардов четыреста восемьдесят восемь миллионов четыреста восемьдесят четыре тысячи четыреста восемьдесят четыре». This string contains 150 characters excluding spaces.

In this problem, it is assumed that for numbers greater than one, the word "один" or "одна" is not written at the beginning of the number, but is written elsewhere. For example, the number 1001001 will be written as "миллион одна тысяча один".

Participants writing in C++ are advised not to use string constants in Russian in their program, as the functions «length» and «strlen» on the server may incorrectly calculate the length of strings with Russian letters (due to Unicode encoding).