Волнистым числом называется такое целое положительное число, что для каждой цифры десятичного представления, не являющейся первой или последней, она либо строго больше обеих соседних с ней цифр, либо строго меньше обеих соседних с ней цифр. Например, числа 35270, 102, 747, 20 и 3 являются волнистыми, а числа 123, 1000 и 2212 — нет.
Для двух заданных целых чисел n и k требуется найти k-е по величине волнистое число r, которое делится нацело на n.
Ваша задача — написать программу для нахождения искомого числа r в случае, если оно не превосходит 1014.
Примечание
Значения первых четырех волнистых чисел кратных n для первого примера входных данных: 492, 615, 738 и 1845.