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.
k,t=map(int,raw_input().split())
klis=list(map(int,raw_input().split()))

for _ in xrange(t):
	ans=0
	a,b=map(int,raw_input().split())
	for i in xrange(1,2**k):
		l,r=a-1,b
		par=0
		for j in xrange(k):
			if(i&(1<<j)):
				par+=1
				l/=klis[j]
				r/=klis[j]
		if(par&1):
			ans+=(r-l)
		else:
			ans-=(r-l)
	print ans