Problems
Divisibility
Divisibility
Given a list of integers a1
, a2
, ..., an
. Find the number of integers between l and r, inclusive, that are divisible by at least one of the elements in a given list.
Input
Consists of multiple test cases. The first line of each test case contains two integers l (1 ≤ l ≤ 109
) and r (1 ≤ r ≤ 109
). Next line contains the number of elements n (1 ≤ n ≤ 18) in a list and a list itself. Each number in a list ranges from 1 to 109
inclusive.
Output
For each tests case print in a separate line the number of integers between l and r inclusive, that are divisible by at least one of the elements a1
, a2
, ..., an
.
Input example #1
293 784 1 1 579000 987654 2 1 2 1 1000000000 2 2 3
Output example #1
492 408655 666666667