Virat is a guy who likes solving problems very much. Today Virat’s friend Jadega gave him a problem to solve. Jadeja gives Virat three numbers: N, L and R and Virat has to find out the count of numbers between L and R (both inclusive) which are divisible by at least 1 prime number belonging to range 1 to N (inclusive).
Though Virat likes to solve problems, this one seems too hard for him to solve. So he turns to you in order to solve the problem. Now it is your job to solve this problem for Virat.

Input

First line of input contains number of test cases T.
Each of next T lines contain 3 space separated integers: N,L and R as described in the problem statement.

Output

For each test case, print a single line having the count of numbers between L and R (both inclusive) which are divisible by at least 1 prime number belonging to range 1 to N (inclusive).

Constraints

1 ≤ T ≤ 10
2 ≤ N ≤ 50
1 ≤ L ≤ R ≤ 10^18

Example
Input
2
6 1 15
10 17 29

Output
11
9

Explanation

In the 1st test case, primes in the range 1 to 6 are 2, 3 and 5. The numbers in the range 1 to 15 which are divisible by any of 2,3 or 5 are 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15 (total 11).

In the 2nd test case, prime in the range 1 to 10 are 2, 3, 5 and 7. The number in the range 17 to 29 which are divisible by any of these primes are 18, 20, 21, 22, 24, 25, 26, 27, 28 (total 9).

见题面

见题面