У Степана есть большое целое положительное число.
Рассмотрим все циклические сдвиги числа, если рассматривать его как строку, которые также являются числами (то есть не начинаются с нуля). Будем называть такие циклические сдвиги хорошими. Например, для числа 10203 хорошими циклическими сдвигами являются само число 10203, а также числа 20310 и 31020.
Степану стало интересно, какой наименьший остаток от деления на заданное число m можно получить, поделив на m все хорошие циклические сдвиги заданного числа.
Выходные данные
Выведите искомый наименьший остаток от деления на число m всех хороших циклических сдвигов заданного числа.
Примечание
В первом примере все хорошие циклические сдвиги числа 521 (они равны 521, 215, 152) дают одинаковый остаток 2 при делении на 3.
Во втором примере для заданного числа есть только два хороших циклических сдвига: на ноль позиций и на одну позицию вправо. Сдвиг на ноль позиций равен 1001 и остаток от деления на 5 равен 1, а сдвиг на одну позицию вправо равен 1100 и остаток от деления на 5 равен 0, который является минимальным возможным остатком.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
521
3
|
2
|
|
2
|
1001
5
|
0
|
|
3
|
5678901234567890123456789
10000
|
123
|