Əlavə sinif

Siz a və b ədədlərinin additiv sinfinə aid olan və [l, r] intervalına düşən elementlərin sayını hesablamalısınız.

Təbii ədədlərin a və b additiv sinfi, hər biri a və ya b olan sıfır və ya daha çox ədədin cəmi şəklində təqdim edilə bilən ədədlər çoxluğudur. Formal olaraq bu çoxluq belədir: {x ∙ a + y ∙ b | x, y Z; x, y ≥ 0}.

Verilən a, b, həmçinin l və r (l ≤ r) ədədlərinə görə, a və b additiv sinfinin l ≤ e ≤ r ikili bərabərsizliyini ödəyən neçə elementi olduğunu tapın.

Giriş verilənləri

Bir neçə testdən ibarətdir. Birinci sətir testlərin sayını t (1 ≤ t ≤ 10 000) göstərir.

Hər test iki sətirdən ibarətdir. Birinci sətir iki təbii ədəd a və b (1 ≤ a, b ≤ 10^9) ehtiva edir. İkinci sətir iki ədəd l və r (0 ≤ l ≤ r ≤ 10^18) ehtiva edir.

Çıxış verilənləri

Hər test üçün ayrıca sətirdə bir ədəd çıxarın: a və b additiv sinfinin [l, r] intervalına aid olan elementlərin sayı.

Nümunələr

Qeyd

İki testi nəzərdən keçirək.

Birinci testdə a = 3 və b = 5. Additiv sinif 0, 3, 5, 6 = 3 + 3, 8 = 3 + 5, 9 = 3 + 3 + 3, ... ədədlərindən ibarətdir. Onlardan ikisi [6, 8] intervalına aiddir.

İkinci testdə a = 6 və b = 4. Additiv sinif yalnız cüt ədədləri ehtiva edir, onlardan heç biri [13, 13] intervalına aid deyil.