Milly likes to solve problems very much. Today she is solving a problem in which she has N, L and R and she has to find out the total count of Magic Numbers in [L, R] . Magic Numbers are the numbers which are divisible by at least one prime number in [1, N] . Being a beginner in programming, this one seems too hard for her to solve. So, she is asking you for her help, so your task is to solve this problem.
Input
First line of the input will have a integer T(number of test cases). Then each of the next T lines will contain 3 space separated integers: N, L and R.
Output
For each test case, print a single line having the count of Magic Numbers in [L, R] .
Constraints
1 ≤ T ≤ 10
2 ≤ N ≤ 50
1 ≤ L ≤ R ≤ 1018
In the 1st test case, primes in the range 1 to 5 are 2, 3 and 5. The numbers in the range 1 to 10 which are divisible by any of 2,3 or 5 are 2, 3, 4, 5, 6, 8, 9, 10, (total 8).
