I. Number builder
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

This will be a simple task. Even more. We like to generate different numbers, we think and you will like it. You are given an integer s. Try to generate the maximum number with the sum of digits equal to s, which does not contain zeros, and also any adjacent digits are not equal.

Input

The single line contains the number s.

1 ≤ s ≤ 42
Output

Output a single number containing the answer to the problem.

Examples
Input
1
Output
1
Input
2
Output
2