Humble numbers

Peter has a list of his favorite odd prime numbers ($P=[P_{1},\ldots,P_{N}]$). A number is called “humble” if it has no prime divisors other than Peter’s favorite primes. He wants to know how many “humble” numbers exist in a given closed interval $[lo,up]$. Answering these questions manually would be very time-consuming, so Peter is trying to write a program to solve them. Unfortunately, he got stuck, so it’s up to you to implement it.

Examples

for P=[3, 5] the first few humble numbers:
1, 3, 5, 9, 15, 25, 27, 45, 75, 81, 125, 135, 225, 243, 375, 405,...
in the interval [10,50] there are 4 humble numbers
in the interval [100,400] there are 5 humble numbers


for P=[7,11,23]  the first few humble numbers::
1, 7, 11, 23, 49, 77, 121, 161, 253, 343, 529, 539, 847, 1127, 1771,...
in the interval [10,50] there are 3 humble numbers
in the interval [100,400]  there are 4 humble numbers

Input specification

The first line containd the number of Peter’s favourite primes. In the next one there $N$ different odd prime numbers. The 3. line contains the number of questions, $Q$ to answer. Each of the next $Q$ lines has two space separated numbers $lo_{q}$ és $up_{q}\ \ q=1\ldots Q$.

Output specification

$Q$ lines with the required answer.

Constraints

$2\le N \le 7$
$1\le Q \le 1\_000$
$1\le lo\le up \le 1\_000\_000\_000\_000$

Sample input 1

1. 2
2. 3 5
3. 5
4. 1 10
5. 11 20
6. 21 30
7. 31 40
8. 41 50

Sample output 1

1. 4
2. 1
3. 2
4. 0
5. 1

Sample input 2

1. 4
2. 3 5 7 11
3. 3
4. 1 1000000
5. 1000001 2000000
6. 2000001 3000000

Sample output 2

1. 447
2. 77
3. 49

Sample input 3

1. 5
2. 3 5 7 11 13
3. 3
4. 1 30000000
5. 30000001 40000000
6. 40000001 60000000

Sample output 3

1. 1974
2. 131
3. 201