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.