Mr M was preparing for interviews of Endurance. Last year he got rejected on an LCM question. So this time he decided to solve as many questions as possible on LCM. He solved the easy questions very fluently but from last few days he's got stuck on the below question :
There are Q queries. For each query you have to answer how many integers m from range [L,R] exists such that LCM(L,L+1,L+2,.......m) <= K. where L,R,K will be given to you.
Help Mr M solve this question. So that he can move ahead in his preparation.
Input Format :
(1) First line contains Q , number of queries
(2) Each of next Q lines contains 3 space separated integers which are L,R,K respectively
Output Format
(1) For each query print single line containing the answer.
Constraints :
1 <= Q <= 2*10^6
1<=L<=R<=10^6
(R-L)<=10^3
0<= K <= 10^18
Setter : Aayush Kapadia
There are 3 test cases :
(1) As given range is [4,6] : lcm(4) = 4 which is less than equals to 20 lcm(4,5) = 20 which is less than equals to 20 lcm(4,5,6) = lcm(20,6) = 60 which is more than 20
So answer is 2.
(2) Given range is [5,7] : lcm(5) = 5 , which is less than equals to 35 lcm(5,6) = 30 , which is less than equals to 35 lcm(5,6,7) = lcm(30,7) = 210 , which is greater than 35
So answer is 2
(3) Given range is [6,6] lcm(6) = 6 which is greater than 5
So answer is 0.
