Аддитивный класс

Вам следует подсчитать количество элементов в аддитивном классе a и b, принадлежащих интервалу [l, r].

Аддитивным классом натуральных чисел a и b называется множество чисел, представимых в виде суммы нуля или более чисел, каждое из которых равно a или b. Формально это следующее множество: {x ∙ a + y ∙ b | x, y Z; x, y ≥ 0}.

По заданным числам a, b, а также l и r (l ≤ r) найдите, сколько элементов e из аддитивного класса a и b удовлетворяют двойному неравенству l ≤ e ≤ r.

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

Состоит из нескольких тестов. Первая строка содержит количество тестов t (1 ≤ t ≤ 10 000).

Каждый тест состоит из двух строк. Первая строка содержит два натуральных числа a и b (1 ≤ a, b ≤ 10^9). Вторая строка содержит два числа l и r (0 ≤ l ≤ r ≤ 10^18).

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

Для каждого теста вывести в отдельной строке одно число: количество элементов в аддитивном классе a и b, принадлежащих отрезку [l, r].

Примеры

Примечание

Рассмотрим два теста.

В первом тесте a = 3 и b = 5. Аддитивный класс состоит из чисел 0, 3, 5, 6 = 3 + 3, 8 = 3 + 5, 9 = 3 + 3 + 3, ... . Два из них принадлежат отрезку [6, 8].

Во втором тесте a = 6 и b = 4. Аддитивный класс содержит только четные числа, ни одно из них не принадлежит отрезку [13, 13].