Stepan 有一个非常大的正整数。
让我们考虑 Stepan 整数的所有循环移位(如果我们像看字符串一样查看他的整数),它们也是整数(即它们没有前导零)。我们将这种转变称为良好的转变。例如,对于整数 10203,好的移位是整数本身 10203 以及整数 20310 和 31020。
Stepan 想知道所有好的移位中除以给定数字 m 的最小余数。你的任务是确定除以 m 的最小余数。
输入
第一行包含 Stepan 拥有的整数。 Stepan 整数的长度介于 2 到 200 000 位数字之间(含 2 和 200 000 位数字)。保证 Stepan 的整数不包含前导零。
第二行包含整数 m (2 ≤ m ≤ 108) — Stepan 将其整数的良好移位除以的数字。
输出
打印 Stepan 将其整数的所有良好移位除以给定数字 m 时可以得到的最小余数。
示例
输入 #1
521 3
输出 #1
2
输入 #2
1001 5
输出 #2
0
输入 #3
5678901234567890123456789 10000
输出 #3
123
注意
在第一个示例中,整数 521 的所有良好移位(良好移位等于 521、215 和 152)除以 3 时具有相同的余数 2。
在第二个示例中,只有两个好的移位:Stepan 整数本身和向右移位一位。整数本身是 1001,除以 5 后的余数等于 1。向右移动一位等于 1100,除以 5 后的余数等于 0,这是可能的最小余数。