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.
The only line contains a single integer n (1 ≤ n ≤ 10^18).
Print the n^{-th} moderate number.