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 solve():
	[k,t] = [int(x) for x in raw_input().split()]
	p = [int(x) for x in raw_input().split()]
	
	for _ in xrange(t):
		[a,b] = [float(x) for x in raw_input().split()]
		r = 0
		
		
		for i in xrange(1,2**k):
			cnt = 0 
			d = 1
			diag=""
			for j in xrange(k):
				if (i & (1<<(j))) > 0:
					cnt += 1
					d = d*p[j]
					diag += str(p[j])+" "
			
			#print cnt,diag,d
				
			if cnt%2 == 0:
				r -= (int(math.floor(b/d))-int(math.ceil(a/d))) + 1
			else:
				r += (int(math.floor(b/d))-int(math.ceil(a/d))) + 1
			
				
		print r
		
solve()