409465: GYM103567 D (Не)достижимый идеал
Description
Недавно Софья Ковалевская прочла про понятие «идеальной пары» целых чисел. Пара целых чисел $$$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)$$$ и, следовательно, в ответе не учитывается.