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 itertools
import sys

def cal(a,b,p):
      d=b-a+1
      t=0
      for i in p:
            if i<0:
                  r=-i
                  t=t-int(d/r)
            else:
                  t=t+int(d/i)
      return t
      
def main():
      I=sys.stdin.readlines()
      p=I[1].split()
      p = map(int, p)
      f=[]
      for L in range(1, len(p)+1):
            for subset in itertools.combinations(p, L):
                  s=1
                  for e in subset:
                        s=s*e
                  if L%2==0:
                        f.append(-s)
                  else:
                        f.append(s)
      r=len(I)-2
      for i in xrange(0,r):
            a,b=I[i+2].split()
            if int(a)==1:
                  print cal(int(a),int(b),f)
            else:
                  t1=cal(1,int(a)-1,f)
                  t2=cal(1,int(b),f)
                  print t2-t1
  
      
main()