A. Минимальная взаимная простота
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Сегодня Маленький Джон потратил все свои сбережения, чтобы купить отрезок. Теперь он хочет построить на нём дом.

Отрезок положительных целых чисел $$$[l,r]$$$ называется взаимно простым, если числа $$$l$$$ и $$$r$$$ взаимно простые$$$^{\text{∗}}$$$.

Взаимно простой отрезок $$$[l,r]$$$ называется минимальным взаимно простым, если он не содержит$$$^{\text{†}}$$$ никаких взаимно простых отрезков, не равных самому себе. Ниже в разделе примечаний приведены примеры минимальных и не минимальных взаимно простых отрезков.

Дан отрезок $$$[l,r]$$$ положительных целых чисел, найдите количество минимальных взаимно простых отрезков, содержащихся в $$$[l,r]$$$.

$$$^{\text{∗}}$$$Два целых числа $$$a$$$ и $$$b$$$ являются взаимно простыми, если у них есть только один положительный общий делитель. Так, например, числа $$$2$$$ и $$$4$$$ не являются взаимно простыми, потому что они оба делятся на $$$2$$$ и $$$1$$$, но числа $$$7$$$ и $$$9$$$ являются взаимно простыми, так как их единственный положительный общий делитель $$$1$$$.

$$$^{\text{†}}$$$Отрезок $$$[l',r']$$$ содержится внутри отрезка $$$[l,r]$$$, если и только если $$$l \le l' \le r' \le r$$$.

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

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

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

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

Для каждого набора входных данных выведите количество минимальных взаимно простых отрезков, содержащихся в $$$[l,r]$$$, в отдельной строке.

Пример
Входные данные
6
1 2
1 10
49 49
69 420
1 1
9982 44353
Выходные данные
1
9
0
351
1
34371
Примечание

В первом наборе входных данных дан отрезок $$$[1,2]$$$. Отрезки, содержащиеся в $$$[1,2]$$$, следующие:

  • $$$[1,1]$$$: Этот отрезок является взаимно простым, так как числа $$$1$$$ и $$$1$$$ являются взаимно простыми, и не содержит никаких других отрезков внутри. Таким образом, $$$[1,1]$$$ является минимальным взаимно простым.
  • $$$[1,2]$$$: Этот отрезок является взаимно простым. Однако, поскольку он содержит $$$[1,1]$$$, который также является взаимно простым, $$$[1,2]$$$ не является минимальным взаимно простым.
  • $$$[2,2]$$$: Этот отрезок не является взаимно простым, потому что числа $$$2$$$ и $$$2$$$ имеют $$$2$$$ общих положительных делителя: $$$1$$$ и $$$2$$$.

Таким образом, отрезок $$$[1,2]$$$ содержит $$$1$$$ минимальный взаимно простой отрезок.