该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

倍数关系

时间限制：$1s$

空间限制：$256MB$

题目描述

定义数$N$是集合$A$的倍数，当且仅当存在A中元素$a_i$，使得$a_i$是$N$的因子，记为$A|N$。

给定一个有$k$个元素的集合$A$与区间$[l,r]$,你需要给出区间内的数$s$的数量，其中$s$不满足满足$A|s$。

保证$|A|$不超过$20$，且$A$中元素均为素数。

数据格式

输入

第一行三个整数$l,r,k$，表示区间和集合元素数量。

第 $2$ 行$k$个整数$x$表示集合$A$的元素。

输出

输出 $1$ 行，表示区间内不能被集合整除的数的数量。

样例

输入1

1 100 8
2 3 5 7 11 13 17 19

输出1

18

输入2

337799823 791052442 20
13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

输出2

262442563

数据范围及约定

$1≤l,r≤10^{18}，A中元素大小不超过10^2,|A|不超过20。$