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¹⁸