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:
from itertools import combinations
from operator import mul
from functools import reduce
K, T = map(int, raw_input().split())
l = map(int, raw_input().split())
for i in xrange(T):
	n, n1 = map(int, raw_input().split())
	n -= 1
	ans, ans1 = 0, 0
	for i in range(1, K+1):
		for j in combinations(l, i):
			if i&1:
				ans += n//reduce(mul, j, 1)
			else:
				ans -= n//reduce(mul, j, 1)
	for i in range(1, K+1):
		for j in combinations(l, i):
			if i&1:
				ans1 += n1//reduce(mul, j, 1)
			else:
				ans1 -= n1//reduce(mul, j, 1)
	print ans1 - ans