Friends I am solving a problem but i am not able to understand how to start it. Any kind of help would be great. The problem statement is below.

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 ≤ 10^18