Egyszerű számok

Péternek van néhány ($P=[P_{1},\ldots,P_{N}]$) kedvenc páratlan prímszáma. Egy számot egyszerűnek nevez, ha a kedvenc prímszámain kívül nincsen más prímosztója. Arra kíváncsi, hogy adot $lo\le up$ számok esetén hány egyszerű szám van a $[lo,up]$ zárt intervallumban. Ezekre a kérdésekre papíron elég hosszadalmas lenne válaszolni, ezért programot próbál írni, de sajnos elakadt, így rátok vár a megvalósítása.

Példák

P=[3, 5] esetén az első néhány egyszerű szám:
1, 3, 5, 9, 15, 25, 27, 45, 75, 81, 125, 135, 225, 243, 375, 405,...
a [10,50] intervallumba 4 egyszerű szám esik
a [100,400] intervallumba 5 egyszerű szám esik


P=[7,11,23] esetén az első néhány egyszerű szám:
1, 7, 11, 23, 49, 77, 121, 161, 253, 343, 529, 539, 847, 1127, 1771,...
a [10,50] intervallumba 3 egyszerű szám esik
a [100,400] intervallumba 4 egyszerű szám esik

Bemenet specifikáció

Az első sorban a kedvenc prímszámok $N$ száma van. A következőben $N$ darab különböző, páratlan prímszám. A harmadikban a megválaszolandó kérdések $Q$ száma van, majd $Q$ sor következik, mindegyikben két számmal: $lo_{q}$ és $up_{q}\ \ q=1\ldots Q$. A számok a sorokon belül üreshellyel elválasztottak.

Kimenet specifikáció

$Q$ sor, a kérdésekre adott válaszokkal.

Korlátok

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

1. példa bemenet

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

1. példa kimenet

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

2. példa bemenet

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

2. példa kimenet

1. 447
2. 77
3. 49

3. példa bemenet

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

3. példa kimenet

1. 1974
2. 131
3. 201