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

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

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