Делимость

Имеется набор целых чисел a[1], a[2], ..., a[n]. Найти количество чисел от l до r включительно, которые делятся хотя бы на одно число из этого набора.

Входные данные

Состоит из нескольких тестов. Первая строка каждого теста содержит два целых числа l (1 ≤ l ≤ 10^9) и r (1 ≤ r ≤ 10^9). Следующая строка содержит количество элементов n (1 ≤ n ≤ 18) в наборе и сам набор этих чисел. Каждое число в наборе принимает значение от 1 до 10^9.

Выходные данные

Для каждого теста в отдельной строке вывести количество чисел от l до r включительно, которые делятся хотя бы на одно из чисел из набора a[1], a[2], ..., a[n].

Примеры