A positive integer is called a moderate number if the product of its digits is equal to their sum. You are given an integer \textbf{n}. Find the \textbf{n}^\{-th\} moderate number. Moderate numbers are numbered starting from \textbf{1}. \InputFile The only line contains a single integer \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^18}). \OutputFile Print the \textbf{n}^\{-th\} moderate number.