В одной очень влиятельной организации для упрощения контроля въезда автотранспорта сотрудников на территорию решили, что автомобильные номера у всех сотрудников должны иметь одинаковое произведение цифр, равное числу N.
Номера в этой стране могут быть любыми натуральными числами, а жители страны очень любят «маленькие» номера — чем меньше число в номере автомобиля, тем более престижным он считается.
Директор организации хочет, чтобы ни у кого из сотрудников не было более престижного номера, чем у него. Поскольку организация очень влиятельная, директор может получить любой номер по своему желанию.
Входные данные
Программа получает на вход одно натуральное число N, не превосходящее 10
18, — произведение
цифр автомобильных номеров сотрудников очень влиятельной организации.
Обратите внимание, значение N может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип long long в языке C++, тип int64 в Pascal, тип long в Java и C#).
Выходные данные
Выведите одно целое число — минимальное значение номера автомобиля директора очень влиятельной организации.
Если ни одного подходящего номера не существует, программа должна вывести число «−1».
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
70 |
257 |
| 2 |
101 |
-1 |