Problem E
Hljóðstilling

Mynd fengin af flickr.com

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\le L\le R\le {10}^{14}$, bilið sem hljómtækið styður og heiltölu $k$, þar sem $1\le k\le 20$. Að lokum kemur ein lína með $k$ heiltölum $a_1,a_2,\dots ,a_k$, uppáhalds tölur Söru. Það gildir fyrir öll $i$ að $2\le a_i\le 7919$ 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

1 30 2
2 5

18

17 100 1
7

12