eolymp
bolt
Try our new interface for solving problems
Problems

Простая задача

Простая задача

Time limit 1 second
Memory limit 128 MiB

Найдите количество натуральных чисел на данном отрезке от a до b включительно, не делящихся нацело ни на одно из заданных различных простых чисел p[i].

Input data

В первой строке заданы два числа a и b (1ab10^18) - границы отрезка. Во второй строке задано количество простых чисел n (1n9). В третьей строке перечислены сами простые числа p[i]. Все числа p[i] различны и не превосходят 100.

Output data

Вывести искомое количество натуральных чисел.

Examples

Input example #1
5 10
2
2 3
Output example #1
2
Input example #2
20 40
2
3 7
Output example #2
12
Input example #3
50 100
1
17
Output example #3
48
Input example #4
100 200
3
2 3 5
Output example #4
28