Given K prime numbers and T queries of form Ai, Bi, for each query print the number of integers between Ai and Bi (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 Ai, Bi.

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

Constraints
1 ≤ K ≤ 10
1 ≤ T ≤ 100
1 ≤ A ≤ B ≤ 10^9
Each prime ≤ 10^7

SAMPLE INPUT
2 1
2 3
1 10

SAMPLE OUTPUT
7

Explanation

2,3,4,6,8,9,10 are the 7 numbers.

见题面

见题面