Пусть $$$x$$$ — целое положительное число. Определим функцию $$$f(x)$$$ следующим образом:
Здесь $$$lcm(a)$$$ обозначает наименьшее общее кратное множества $$$a$$$, то есть минимальное целое положительное число, делящееся нацело на каждый из элементов множества $$$a$$$.
Даны положительные целые числа $$$l$$$ и $$$r$$$. Необходимо найти количество различных значений $$$f(i)$$$ среди $$$l \leq i \leq r$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — количество наборов входных данных. Далее следует их описание.
Единственная строка каждого набора входных данных содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq 10^7$$$).
Для каждого набора входных данных выведите количество различных значений $$$f(i)$$$ среди $$$l \leq i \leq r$$$ в отдельной строке.
211 141 5
25
В первом наборе входных данных значения $$$f(i)$$$ для $$$i \in [11, 14]$$$ равны $$$27720, 27720, 360360, 360360$$$. Среди этих четырех чисел — два различных, поэтому ответ равен $$$2$$$.
Во втором наборе входных данных для $$$i \in [1, 5]$$$ все значения $$$f(i)$$$ различны, поэтому ответ равен $$$5$$$.