음량 설정

사진 출처

Sara는 친구들과 차를 타고 갈 때 자주 음악을 듣는다. 다음은 어느 특정한 자동차 여행에서 나눈 대화의 기록이다.

**SARA:** ``Tónlist eða?''

**HANNES:** ``Ehaggi!''

**ARNAR:** ``Hey Google! Play Despacito!''

*Hannes가 재빨리 음량을 조절한다.*

**SARA:** ``HVERNIG DIRFISTU AÐ STILLA HLJÓÐIÐ Á 11?!?!? 11 ER EKKI DEILANLEG MEÐ NEINUM AF UPPÁHALDSTÖLUNUM MÍNUM!!!''

Sara는 오디오의 음량 설정값이 자신이 좋아하는 수 중 적어도 하나로 나누어떨어지지 않으면 도저히 견딜 수 없기 때문이다. 예를 들어 Sara가 좋아하는 수가 $2$와 $5$라면 음량을 $15$, $18$, $20$로 설정하는 것은 허용되지만, $11$, $17$, $21$는 허용되는 값이 아니다. 모두의 삶을 단순하게 하기 위해 Sara는 소수만 좋아할 수 있다.

오디오마다 설정할 수 있는 음량의 범위는 다르지만, 오디오는 정수만 지원한다. 오디오가 지원하는 범위와 Sara가 좋아하는 수들이 주어질 때, Sara가 만족할 수 있는 음량 설정값이 몇 개 있는지 구할 수 있는가?

채점

그룹 | 점수 | 제한

1 | 20 | $R-L \leq 10\,000$

2 | 20 | $k = 1$

3 | 15 | $k \leq 2$

4 | 15 | $k \leq 3$

5 | 30 | 추가 제한 없음.

오디오가 지원하는 범위를 나타내는 정수 $L$와 $R$가 주어지며, 이때 $1 \leq L \leq R \leq 10^{14}$이다. 또한 정수 $k$가 주어지며, 이때 $1 \leq k \leq 20$이다. 마지막으로 Sara가 좋아하는 수인 $k$개의 정수 $a_1, a_2, \dotsc, a_k$가 한 줄에 주어진다. 모든 $i$에 대해 $2 \leq a_i \leq 7\,919$이고, $a_i$는 소수이다.

이 오디오에서 Sara가 만족할 수 있는 음량 설정값의 개수를 나타내는 정수 $n$ 하나를 출력한다.