eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

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

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

Giriş verilənləri

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

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
2
3 5
6 8
6 4
13 13
Çıxış verilənləri #1
2
0

Qeyd

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

В первом тесте 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].

Mənbə 2014 Петрозаводск, Ivan Kazmenko Contest, Август 22, Задача A