Persistent Numbers

Time limit1sMemory limit128 MB

Summary
For each big integer N, find the smallest multi-digit number whose digits multiply to N, or report that none exists.
Level

Medium6 of 10

Topics
Greedy, Math, Number theory, Implementation
Solved
No attempts yet

Problem

The multiplicative persistence of a number, defined by Neil J. A. Sloane in The Persistence of a Number (Journal of Recreational Mathematics 6, 1973, pp. 97–98), is the number of steps needed to reach a single-digit number when you repeatedly replace the number by the product of its digits. For example,

679 → 378 → 168 → 48 → 32 → 6

so the persistence of 679 is 5. The persistence of a single-digit number is 0. It is known that numbers with persistence 11 exist. It is not known whether any number has persistence 12, but if one exists, its smallest instance would have more than 3000 digits.

Your task is different: given a non-negative integer NN, find the smallest positive integer MM whose digits multiply to exactly NN. In other words, MM is the smallest number for which the very first step of computing its persistence yields NN. Because that first step must actually be performed, MM must have at least two digits.

Input

The input consists of several test cases. Each test case is a single line containing one decimal integer with up to 1000 digits. A line containing -1 follows the last test case and is not itself a test case.

Output

For each test case, print a single line containing the smallest number MM described above. If no such number exists, print exactly:

There is no such number.

Examples1

  1. Example 1

    Input
    0
1
4
7
18
49
51
768
-1
    Expected output
    10
11
14
17
29
77
There is no such number.
2688