Hide

Problem E
Hljóðstilling

Languages en is

/problems/hljodstilling/file/statement/en/img-0001.jpg

Image from flickr.com

Sara often listens to music when driving with friends. Here follows a transcript of one such car ride.

SARA: “Music right?”
HANNES: “Yeeea!”
ARNAR: “Hey Google! Play Despacito!”
Hannes corrects the volume quickly.
SARA: “HOW DARE YOU SET THE VOLUME TO ELEVEN?!?!?! 11 IS NOT DIVISIBLE BY ANY OF MY FAVOURITE NUMBERS!!!”

Sara despises it when the volume is set to a number not divisible by at least one of her favourite numbers. For example if her favourite numbers were $2$ and $5$ it’d be fine to set the volume to $15$ , $18$ or $20$ but $11$ , $17$ or $21$ would not be okay. To simplify the life of everyone involved, Sara’s favourite numbers are always prime.

It depends on the radio model what range of volumes are offered, but all volume settings are always integers. Given the interval that the radio supports and Sara’s favourite numbers, can you say how many volume settings are possible that she’d be alright with?

Input

Integers $L$ and $R$ where $1 \leq L \leq R \leq 10^{14}$ , the interval that the radio supports, and in integer $k$ where $1 \leq k \leq 20$ . Finally a single line with $k$ integers $a_{1}, a_{2}, \dots, a_{k}$ , Sara’s favourite numbers. It will hold for all $i$ that $2 \leq a_{i} \leq 7 919$ and $a_{i}$ is prime.

Output

A single integer $n$ , the number of volume settings that Sara is alright with on this radio.

Scoring

Group	Points	Constraints
1	20	$R - L \leq 10 000$
2	20	$k = 1$
3	15	$k \leq 2$
4	15	$k \leq 3$
5	30	No further constraints.

Sample Input 1	Sample Output 1
1 30 2 2 5	18

Sample Input 2	Sample Output 2
17 100 1 7	12

Problem EHljóðstilling

Input

Output

Scoring

Problem E
Hljóðstilling