Адитивний клас#7315
Визначте, скільки елементів адитивного класу чисел і потрапляють у відрізок [l; r].
Адитивний клас додатних чисел і — це множина чисел, які можна представити у вигляді суми нуля або більше доданків, кожен з яких дорівнює або . Формально:
Дано числа , , а також цілі числа та (l \leq r). Знайдіть кількість елементів e \in S(a, b), які задовольняють нерівності l \le e \le r.
Перший рядок містить ціле число (1 \le t \le 10000) — кількість тестів.
Далі наведені описи тестів. Кожен тест складається з двох рядків:
перший рядок містить два додатних числа і (1 \le a, b \le 10^9);
другий рядок містить два цілі числа і (0 \le l \le r \le 10^{18}).
Для кожного тесту виведіть одне ціле число — кількість елементів адитивного класу S(a, b), що належать відрізку [l; r].
Приклад 1