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

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

p=map(int,raw_input().split())

while t>0:
  a,b=map(int,raw_input().split())
  lo=[]
  le=[]
  for i in xrange(1,k+1):
      for j in itertools.combinations(p,i):
          div=1
          for ml in j:
              div=div*ml
          if i%2==1:
              lo.append(b/div-(a-1)/div)
          else:
              le.append(b/div-(a-1)/div)
  print sum(lo)-sum(le)
  t=t-1