eolymp
bolt
Try our new interface for solving problems
Problems

Divisibility

Divisibility

Time limit 1 second
Memory limit 128 MiB

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 (1l10^9) and r (1r10^9). Next line contains the number of elements n (1n18) 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