Аки любит числа. Особенно те, что заканчиваются на большое количество нулей. Например, число \(9200\) заканчивается на два нуля. Аки считает, что чем больше таких замыкающих нулей в записи числа, тем лучше.
Однако Аки полагает, что количество замыкающих нулей не постоянно, а зависит от основания системы счисления, которая используется. Поэтому он изучает различные сценарии с разными числами и разными основаниями систем счисления. К настоящему моменту интересующие его числа стали настолько странными, что без вашей помощи ему никак не обойтись.
Вам даны два целых числа \(n\) и \(b\) (записанные в десятичной системе счисления). Выясните, сколько замыкающих нулей в \(b\)-ичной (то есть в системе счисления с основанием \(b\)) записи числа \(n\,!\) (факториала \(n\)).
Выходные данные
Выведите одно целое число — количество замыкающих нулей в \(b\)-ичной записи числа \(n!\).
Примечание
В первом примере \(6!_{(10)} = 720_{(10)} = 880_{(9)}\).
Во втором и третьем примерах \(5!_{(10)} = 120_{(10)} = 1111000_{(2)}\).
Последовательность \(d_1, d_2, \ldots, d_k\) называется представлением числа \(x\) в \(b\)-ичной системе счисления, если \(x = d_1 b^{k - 1} + d_2 b^{k - 2} + \ldots + d_k b^0\), где \(d_i\) являются целыми числами и \(0 \le d_i \le b - 1\). Например, число \(720\) из первого примера имеет представление \(880_{(9)}\) так как \(720 = 8 \cdot 9^2 + 8 \cdot 9 + 0 \cdot 1\).
Вы можете прочитать ещё о системах счисления здесь.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 9
|
1
|
|
2
|
38 11
|
3
|
|
3
|
5 2
|
3
|
|
4
|
5 10
|
1
|