All Tracks Problem

Milly and the Magic Numbers
Tag(s):

Algorithms, Bitmask, Easy-Medium

Problem
Editorial
Analytics

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

SAMPLE INPUT
2
5 1 10
10 10 20
SAMPLE OUTPUT
8
7
Explanation

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).

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Globalsoft

Challenge Name

Globalsoft Backend Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications