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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# https://www.hackerearth.com/problem/algorithm/count-numbers-7/

K, T = [int(x) for x in raw_input().split()]
primes = [int(x) for x in raw_input().split()]


def count_of_divisible(x):
    result = 0
    for i in xrange(0, 1 << K):
        j = i
        product = 1
        k = 0
        count_of_ones = 0
        while j > 0:
            if j & 1:
                product *= primes[k]
                count_of_ones += 1
            k += 1
            j >>= 1
        if count_of_ones & 1:
            result -= x // product
        else:
            result += x // product
    return x - result

for i in xrange(0, T):
    A, B = [int(x) for x in raw_input().split()]
    print(count_of_divisible(B) - count_of_divisible(A - 1))