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
k, t = map(int, raw_input().split())
K = sorted(map(int, raw_input().split()))
D = {}
def sol(x, y, z):
	a = y/z - x/z
	if x % z == 0:
		a += 1
	return a
for _ in xrange(t):
	u, v = map(int, raw_input().split())
	ans = 0
	for i in xrange(1, k + 1):
		for x in combinations(K, i):
			num = 1
			for y in x:
				num *= y
			if i % 2 == 1:
				ans += sol(u, v, num)
			else:
				ans -= sol(u, v, num)
	print ans