Hide

Problem E
Hljóðstilling

Languages en is
/problems/hljodstilling/file/statement/is/img-0001.jpg
Mynd fengin af flickr.com
Sara hlustar oft á tónlist í bílferðum með vinum sínum. Hér fylgir rit um samskipti í einni tiltekinni bílferð.
SARA: “Tónlist eða?”
HANNES: “Ehaggi!”
ARNAR: “Hey Google! Play Despacito!”
Hannes stillir hljóðið í fljótu bragði.
SARA: “HVERNIG DIRFISTU AÐ STILLA HLJÓÐIÐ Á 11?!?!? 11 ER EKKI DEILANLEG MEÐ NEINUM AF UPPÁHALDSTÖLUNUM MÍNUM!!!”

Söru finnst nefnilega alveg ómögulegt þegar hljóðstillingin á hljómtækinu er ekki deilanleg með allavega einni af uppáhaldstölunum sínum. Til dæmis ef uppáhalds tölurnar hennar Söru væru $2$ og $5$ þá væri leyfilegt að stilla hljóðið á $15$, $18$ eða $20$ en $11$, $17$ eða $21$ væru ekki leyfileg gildi. Til að einfalda líf allra þá geta einungis frumtölur verið í uppáhaldi hjá Söru.

Það er mismunandi eftir hljómtækjum á hvaða bili er hægt að stilla hljóðið, en hljómtæki styðja einungis heiltölur. Gefið bilið sem hljómtækið styður og uppáhalds tölurnar hennar Söru geturðu sagt hvað eru margar hljóðstillingar í boði sem hún væri sátt með?

Inntak

Heiltölur $L$ og $R$, þar sem $1 \leq L \leq R \leq 10^{14}$, bilið sem hljómtækið styður og heiltölu $k$, þar sem $1 \leq k \leq 20$. Að lokum kemur ein lína með $k$ heiltölum $a_1, a_2, \dotsc , a_k$, uppáhalds tölur Söru. Það gildir fyrir öll $i$$2 \leq a_i \leq 7\, 919$ og $a_i$ er frumtala.

Úttak

Ein heiltala $n$, fjöldi hljóðstillinga sem Sara er sátt með á þessu hljómtæki.

Stigagjöf

Hópur

Stig

Takmarkanir

1

20

$R-L \leq 10\, 000$

2

20

$k = 1$

3

15

$k \leq 2$

4

15

$k \leq 3$

5

30

Engar frekari takmarkanir.

Sample Input 1 Sample Output 1
1 30 2
2 5
18
Sample Input 2 Sample Output 2
17 100 1
7
12