Имеется набор целых чисел a1, a2, ..., an. Найти количество чисел от l до r включительно, которые делятся хотя бы на одно число из этого набора.

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

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

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

Для каждого теста в отдельной строке вывести количество чисел от l до r включительно, которые делятся хотя бы на одно из чисел a1, a2, ..., an.