Given K prime numbers and T queries of form A_i, B_i, for each query print the number of integers between A_i and B_i (both inclusive) that are divisible by atleast one of the K given primes.

Input
First line: K and T.
Second line: K primes.
Next T lines, each contain A_i, B_i.

Output
Print T lines, denoting the answer to each of the T queries.

Constraints
1 ≤ K ≤ 10
1 ≤ T ≤ 100
1 ≤ A ≤ B ≤ 10⁹
Each prime ≤ 10⁷