E. Нули на конце факториала
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для всех целых положительных чисел $$$x\ge 1$$$ и $$$k\ge 2$$$, пусть $$$v_k(x!)$$$ обозначает количество нулей на конце представления $$$x! = x\cdot (x-1)\cdot \ldots \cdot 1$$$ в системе счисления с основанием $$$k$$$. Формально, $$$v_k(x!)$$$ определяется как наибольшее целое число $$$i$$$, такое что $$$k^i$$$ делит $$$x!$$$.

Можно показать, что для любого простого числа $$$p$$$ верно следующее: $$$v_p(x!) = \sum\limits_{j=1}^\infty \left\lfloor \frac{x}{p^j}\right\rfloor$$$$$$^{\text{∗}}$$$. А если $$$k$$$ не является простым, разложим его на множители: $$$k = \prod p_i^{e_i}$$$, где $$$p_i$$$ — различные простые множители, а $$$e_i$$$ — соответствующие им показатели. Тогда $$$$$$v_k(x!) = \min\limits_i \left\lfloor \frac{v_{p_i}(x!)}{e_i}\right\rfloor.$$$$$$

Для любых двух целых положительных чисел $$$a$$$ и $$$b$$$, и любого целого числа $$$k\ge 2$$$, вес пары $$$(a, b)$$$ относительно $$$k$$$, обозначаемый как $$$w_k(a, b)$$$, определяется следующим образом:

$$$$$$w_k(a, b) = \begin{cases}\min(v_k(a!), v_k(b!))\text{,} & \text{если }v_k(a!)\neq v_k(b!)\text{;}\\10^{100} & \text{в противном случае.}\end{cases}$$$$$$

Далее, определим $$$f_m(a, b)$$$ как минимальный вес пары $$$(a, b)$$$ относительно $$$k$$$, взятый по всем целым числам $$$k$$$ с $$$2\le k\le m$$$: $$$$$$f_m(a, b)=\min\limits_{2\le k\le m}w_k(a, b).$$$$$$

Вам даны два целых числа $$$n$$$ и $$$m$$$. Ваша задача — вычислить сумму $$$f_m(x, n)$$$ по всем положительным целым числам $$$x$$$, меньшим $$$n$$$: $$$$$$\sum_{1\le x\le n - 1} f_m(x, n).$$$$$$

Можно показать, что при заданных ограничениях результат будет строго меньше $$$10^{100}$$$.

$$$^{\text{∗}}$$$$$$\lfloor y\rfloor$$$ обозначает округление вниз значения $$$y$$$ до ближайшего целого числа, то есть наибольшее целое число, не превосходящее $$$y$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая и единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2\le n\le m\le 10^7$$$) — параметры функции.

Обратите внимание, что нет дополнительного ограничения на сумму $$$n, m$$$ по всем наборам входных данных.

Выходные данные

Для каждого набора входных данных выведите одно целое число — значение $$$\sum\limits_{1\le x\le n - 1} f_m(x, n)$$$.

Пример
Входные данные
5
3 5
6 7
6 10
36 68
10000000 10000000
Выходные данные
0
1
0
13
279933
Примечание

В первом наборе входных данных рассмотрим $$$k = 3\le 5$$$:

  • $$$v_3(1!) = v_3(2!) = 0$$$, так как $$$3$$$ не делит ни $$$1$$$, ни $$$2$$$.
  • $$$v_3(3!) = v_3(6) = 1$$$, так как $$$3$$$ делит $$$6$$$, но не делит $$$3^2 = 9$$$.

Следовательно, $$$w_3(1, 3) = w_3(2, 3) = \min(0, 1) = 0$$$. Можно показать, что это минимальный вес среди всех $$$2\le k\le 5$$$, поэтому $$$f_5(1, 3) = f_5(2, 3) = 0$$$.

Во втором наборе входных данных можно показать, что $$$f_7(1, 6) = f_7(2, 6) = f_7(3, 6) = f_7(4, 6) = 0$$$. Для $$$f_7(5, 6)$$$ рассмотрим $$$k = 6\le 7$$$:

  • $$$v_6(5!) = v_6(120) = 1$$$, так как $$$6$$$ делит $$$120$$$, но $$$6^2 = 36$$$ не делит.
  • $$$v_6(6!) = v_6(720) = 2$$$, так как $$$6^2 = 36$$$ делит $$$720$$$, но $$$6^3 = 216$$$ не делит.

Следовательно, $$$w_6(5, 6) = \min(1, 2) = 1$$$. Можно показать, что это минимальный вес среди всех $$$2\le k\le 7$$$, поэтому $$$f_7(5, 6) = 1$$$.

Примечание: выбор $$$k = 7 \le 7$$$ не работает, потому что $$$v_7(5!) = v_7(6!) = 0$$$, поэтому $$$w_7(5, 6) = 10^{100}$$$.

В третьем наборе входных данных можно показать, что $$$f_{10}(1, 6) = f_{10}(2, 6) = f_{10}(3, 6) = f_{10}(4, 6) = 0$$$. Для $$$f_{10}(5, 6)$$$ рассмотрим $$$k = 9\le 10$$$:

  • $$$v_9(5!) = v_9(120) = 0$$$, так как $$$9$$$ не делит $$$120$$$.
  • $$$v_9(6!) = v_9(720) = 1$$$, так как $$$9$$$ делит $$$720$$$, но $$$9^2 = 81$$$ не делит.

Следовательно, $$$w_9(5, 6) = \min(0, 1) = 0$$$. Можно показать, что это минимальный вес среди всех $$$2\le k\le 10$$$, поэтому $$$f_{10}(5, 6) = 0$$$.