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).
from itertools import combinations as c
def primes(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
    return [2] + [i for i in xrange(3,n,2) if sieve[i]]

for i in range(input()):
	n,l,r = map(int,raw_input().split())
	p = primes(n+1)
	su = 0
	for item in p:
		a = r/item  -  (l-1)/item
		su += a
	to_sub = 0
	ll = len(p)
	for i in range(ll):
		for j in range(i+1,ll):
		#print comb
			pro = p[i]*p[j]
			a = (r/pro)
			b = ((l-1)/pro)
			#print l,pro,l/pro
			to_sub += a-b
		#print to_sub
	print su-to_sub