409465: GYM103567 D (Не)достижимый идеал

D. (Не)достижимый идеалограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Недавно Софья Ковалевская прочла про понятие «идеальной пары» целых чисел. Пара целых чисел $$$a$$$ и $$$b$$$ называется идеальной, если $$$\gcd(a, b) = \min(a, b)$$$, где $$$\gcd$$$ — наибольший общий делитель двух целых чисел.

Теперь Софья не может уснуть, пока не узнает количество чисел из полуинтервала $$$[l, r)$$$, образующих идеальную пару с числом $$$n$$$. Помогите ей обрести покой на ближайшую ночь.

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

В первой строке записано одно целое число $$$t$$$ $$$(1 \le t \le 10^4)$$$  — количество ночей, в которые Софья не может уснуть. Далее следуют $$$t$$$ наборов входных данных.

Каждый набор входных данных состоит из одной строки, содержащей три целых числа $$$n$$$, $$$l$$$, $$$r$$$ $$$(1 \le n \le l < r \le 10^{18})$$$ — число, для которого необходимо найти количество идеальных пар, и границы полуинтервала соответственно.

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

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

ПримерВходные данные

4
1 2 3
5 5 15
2 2 3
1 1 1000000000000000000

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

1
2
1
999999999999999999

Примечание

В первом примере $$$\gcd(1, 2) = \min(1, 2) = 1$$$. Других чисел в полуинтервале нет, поэтому ответ равен $$$1$$$.

Во втором примере $$$\gcd(5, 5) = \min(5, 5) = 5$$$, $$$\gcd(5, 10) = \min(5, 10) = 5$$$. Несмотря на то, что число $$$15$$$ подходит числу $$$5$$$, оно не входит в полуинтервал $$$[5,15)$$$ и, следовательно, в ответе не учитывается.