Problem: 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.

Solution (in PYTHON):

Solution:
def get(n, low, high):
    div_h = high // n
    div_l = max(0, low - 1) // n
    return div_h - div_l

def stupid(primes, low, high):
    ret = 0
    for i in xrange(low, high + 1):
        is_div = False
        for p in primes:
            if i % p == 0:
                is_div = True
        ret += is_div
    return ret

k, t = map(int, raw_input().split())
primes = list(map(int, raw_input().split()))

for _ in xrange(t):
    low, high = map(int, raw_input().split())
    answer = 0

    for i in xrange(1, 1 << k):
        cur = 1
        par = 0
        for j in xrange(k):
            if (1 << j) & i:
                par = 1 - par
                cur *= primes[j]

        val = (1 if par == 1 else -1) * get(cur, low, high)
        answer += val

    print answer