Problems

# Divisibility

# Divisibility

Given a list of integers `a[1]`

, `a[2]`

, ..., `a[n]`

. 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 data

Consists of multiple test cases. The first line of each test case contains two integers l (1 ≤ l ≤ `10^9`

) and r (1 ≤ r ≤ `10^9`

). 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 `10^9`

inclusive.

## Output data

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 `a[1]`

, `a[2]`

, ..., `a[n]`

.

## Examples

Input example #1

293 784 1 1 579000 987654 2 1 2 1 1000000000 2 2 3

Output example #1

492 408655 666666667