Задача 5. Забытое число ≡

Условие

Денис перед сном придумал очень замечательное число, но на утро забыл его. Он помнит лишь, что наибольший общий делитель всех цифр числа равен d, а наименьшее общее кратное всех цифр числа равно k. Также, Денис себя хорошо знает и уверен, что он бы выбрал наименьшее число, которое больше l. Помогите Денису вспомнить это число.

Формат входных данных

В строке записано три целых числа d, k и l — наибольший общий делитель всех цифр числа, наименьшее общее кратное все цифр числа и число-ограничение соответственно.

Формат выходных данных

Выведите единственное число — наименьшее число, большее l, которое имеет наибольший общий делитель цифр числа равный d и наименьшее общее кратное равное k.

Ограничения

1 ≤ d ≤ 9

1 ≤ k ≤ 2520

1 ≤ l ≤ 10⁷

Примеры тестов

1 42 441

617

Разбор

Банальное решение:

Алгоритмы нахождения НОК, НОД давно известны, поэтому про них говорить мы не будем

Перебирая все возможные числа начиная с l + 1, проверяем НОК и НОД каждого числа и сравнивая их с полученными изначально.

Так же нужно пропускать все числа, в которых есть 0.