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:
import math
def func1(a,k,A):
    ans=0
    for i in range((1<<k)-1):
        z=i+1
        prod=1;
        for j in range(k):
            if z&(1<<j):
                prod*=A[j]
        if bin(z).count("1")%2==0:
            ans=int(ans-int(int(a)/int(prod)))
        else:
            ans=int(ans+int(int(a)/int(prod)))
    return ans
        

def main():
    k,t=map(int,raw_input().split())
    A=[int(x) for x in raw_input().split()]
    for i in range(t):
        a,b=map(int,raw_input().split())
        a1=func1(a-1,k,A)
        a2=func1(b,k,A)
        print(a2-a1)

if __name__=='__main__':
    main()