Вам следует подсчитать количество элементов в аддитивном классе \textbf{a} и \textbf{b}, принадлежащих интервалу \[\textbf{l}, \textbf{r}\]. \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} Аддитивным классом натуральных чисел \textbf{a} и \textbf{b} называется множество чисел, представимых в виде суммы нуля или более чисел, каждое из которых равно \textbf{a} или \textbf{b}. Формально это следующее множество: \{\textbf{x }∙ \textbf{a} + \textbf{y} ∙ \textbf{b} | \textbf{x}, \textbf{y} \textbf{Z}; \textbf{x}, \textbf{y} ≥ \textbf{0}\}. По заданным числам \textbf{a}, \textbf{b}, а также \textbf{l} и \textbf{r} (\textbf{l} ≤ \textbf{r}) найдите, сколько элементов \textbf{e} из аддитивного класса \textbf{a} и \textbf{b }удовлетворяют двойному неравенству \textbf{l} ≤ \textbf{e} ≤ \textbf{r}. \InputFile Состоит из нескольких тестов. Первая строка содержит количество тестов \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{10 000}). Каждый тест состоит из двух строк. Первая строка содержит два натуральных числа \textbf{a} и \textbf{b} (\textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{10^9}). Вторая строка содержит два числа \textbf{l} и \textbf{r} (\textbf{0} ≤ \textbf{l} ≤ \textbf{r} ≤ \textbf{10^18}). \OutputFile Для каждого теста вывести в отдельной строке одно число: количество элементов в аддитивном классе \textbf{a} и \textbf{b}, принадлежащих отрезку \[\textbf{l}, \textbf{r}\]. \Note Рассмотрим два теста. В первом тесте \textbf{a} = \textbf{3} и \textbf{b} = \textbf{5}. Аддитивный класс состоит из чисел \textbf{0}, \textbf{3}, \textbf{5}, \textbf{6} = \textbf{3} + \textbf{3}, \textbf{8} = \textbf{3} + \textbf{5}, \textbf{9} = \textbf{3} + \textbf{3} + \textbf{3}, ... . Два из них принадлежат отрезку \[\textbf{6}, \textbf{8}\]. Во втором тесте \textbf{a} = \textbf{6} и \textbf{b} = \textbf{4}. Аддитивный класс содержит только четные числа, ни одно из них не принадлежит отрезку \[\textbf{13}, \textbf{13}\].