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 precompute(bin_dict):
    for k in range(1,11):
        for i in range(1,2**k):
            binary = bin(i)[2:].zfill(k)
            ones   = binary.count('1')
            bin_dict[k].append((binary,ones))
        
bin_dict=[[] for x in range(11)]
precompute(bin_dict)
K , T = [int(x) for x in raw_input().split()]
K_primes = [int(x) for x in raw_input().split()]
nums=[]
for bin_tuple in bin_dict[K]:
    mult = 1
    for j in range (K):
        if bin_tuple[0][j]=='1':
            mult*=K_primes[j]
    nums.append((mult,bin_tuple[1]))
 
            

for t in range(T):
    A,B = [int(x) for x in raw_input().split()]
    ans =0
    for item in nums:
    
        res = (B//item[0] - A//item[0])
        if A%item[0] ==0:
            res+=1
        if item[1]%2==0:
            ans-=res
        else:
            ans+=res
    print ans