E. Джоске и полный граф
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Джоске в подарок от дедушки получил огромный неориентированный взвешенный полный$$$^\dagger$$$ граф $$$G$$$, который содержит $$$10^{18}$$$ вершин. Особенность подарка в том, что вес ребра между различными вершинами $$$u$$$ и $$$v$$$ равен $$$\gcd(u, v)^\ddagger$$$. Джоске решил поэкспериментировать и сделать новый граф $$$G'$$$. Для этого он выбирает два целых числа $$$l \le r$$$, и оставляет только такие вершины $$$v$$$, что $$$l \le v \le r$$$, а также оставляет только ребра между оставшимися вершинами.

Теперь Джоске интересуется, сколько различных весов ребер в графе $$$G'$$$. Так как граф получился огромный, он просит вашей помощи.

$$$^\dagger$$$ Полным графом называется простой неориентированный граф, в котором каждая пара различных вершин смежна.

$$$^\ddagger$$$ $$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$, $$$l \le 10^9$$$).

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

Для каждого набора входных данных выведите единственное число — количество различных весов среди оставшихся ребер.

Пример
Входные данные
7
2 4
16 24
2 6
1 10
3 3
2562 2568
125 100090
Выходные данные
2
6
3
5
0
5
50045
Примечание
Графа $$$G'$$$ для первого набора входных данных.

На рисунке видно, что в графе $$$2$$$ различных веса ребер.

В пятом наборе входных данных остается лишь одна вершина, из которой не исходит ни одного ребра, поэтому ответ — $$$0$$$.