Программирование Последовательность чисел

Напишите программу, которая в последовательности натуральных чисел определяет минимальное число, которое при делении на число 112 дает в остатке число, меньшее 9. Программа на вход получается количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, которое при делении на число 112 дает в остатке число, меньшее 9.

Количество чисел не превышает 1000. Введенные числа не превышают 30 000. Программа должна вывести одно число: минимальное число, которое при делении на число 112 дает в остатке число, меньшее 9.

Пример работы программы:

Входные данные	Выходные данные
5 112 10 35 145 225	112