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 padded_bin(i, width):
    s = bin(i)
    return (s[:2] + s[2:].zfill(width))


def main():
	K, T = raw_input().split()
	k, t = int(K), int(T)
	primes = []
	list1 = raw_input().split()
	for i in xrange(k):
		primes.append(int(list1[i]))
	for _ in xrange(t):
		A, B = raw_input().split()
		a, b = int(A), int(B)
		
		ans = 0
		for i in xrange(1, 2**k): 
			counter = 0
			a_c = a - 1
			b_c = b
			bit = padded_bin(i, k)[2:]
			bit = str(bit)
			for j in xrange(k):
				if bit[j] == '1':
					counter += 1
					a_c /= primes[j]
					b_c /= primes[j]
			if counter%2 == 0:
					ans -= (b_c - a_c)
			else:
					ans += (b_c - a_c)
		print ans
	return 0	
	
if __name__ == "__main__":
	main()