All Tracks Problem

Interval count
Tag(s):

Easy, Math, Number Theory

Problem
Editorial
Analytics

This problem of Oz is very straight forward. You are given N distinct prime integers i.e p1, p2,..., pN and an interval [L,R]. Calculate number of integers in this interval that are divisible by at least one of the given primes.

Input :
First line of input contain an integer T — the number of test cases. T tests follow. First line of each test case contain 3 integers — N, L, R. and the next line contains N distinct prime integers - p1, p2,..., pN.

Output :
For each test case output a single number — number of integers in [L,R], that are divisible by at least one of the given primes.

Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 10
1 < pi < 1000 where i=1,2..N
1 ≤ L ≤ R ≤ 1018

SAMPLE INPUT
2
1 1 10
3
2 1 10
2 3
SAMPLE OUTPUT
3
7
Explanation

For second sample :
Numbers in the interval [1,10] which are divisible by at least one prime from (2,3) are as follow :
2, 3, 4, 6, 8, 9, 10

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

Notifications
View All Notifications