Є набір цілих чисел a1, a2, ..., an. Знайти кількість чисел від l до r включно, які діляться хоча б на одне число із цього набору.

Вхідні дані:

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

Вихідні дані:

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