Moderate Numbers
Hard
Execution time limit is 1 second
Runtime memory usage limit is 256 megabytes
A positive integer is called a moderate number if the product of its digits is equal to their sum. You are given an integer n. Find the n^{-th} moderate number. Moderate numbers are numbered starting from 1.
Input
The only line contains a single integer n (1 ≤ n ≤ 10^18).
Output
Print the n^{-th} moderate number.
Examples
Input #1
Answer #1
Submissions 31
Acceptance rate 10%