policefm

In order to avoid the interception of radio talks during important missions, the NYPD cops decided to change the radio frequency they use for talking amongst themselves or with the dispatch very often. In order to transmit the new radio frequency fast and secure, this has to be encoded prior to its transmission. Knowing that perpetrators aren't good at math or computers, the cops thought about sending a non-zero positive integer n, and the new frequency would be given by the product p of n's digits The only problem that has to be worked out is that of finding out positive integer n fast which also has to be the smallest possible of all non-zero positive integers that have the products of their digits equal to p.

Task

Being given a positive integer p, determine the smallest non-zero positive integer n which has the product of its digits equal to p.

Input Data

Input file policefm.in contains on the first line the integer p.

Output Data

Output file policefm.out will contain on line one the requested number n, or a 0 if there is no non-zero positive integer n with the property requested.

Restrictions

Examples

policefm.in policefm.out policefm.in policefm.out policefm.in policefm.out
81 99 101 0 480 2568

Time limit: 0.1 seconds/test

lect. drd. Radu Boriga
"Titu Maiorescu" University - Bucharest
Contact:r_boriga@yahoo.com