In this problem, you have to find how many elements of the additive class of \textbf{a} and \textbf{b} belong to \[\textbf{l}, \textbf{r}\]. \includegraphics{https://static.e-olymp.com/content/a0/a01d6fe5baf86fd274dfc5600a30f76cc672dd3c.jpg} An additive class of positive integers \textbf{a} and \textbf{b} is the set of numbers representable as a sum of zero or more numbers each of which is either \textbf{a} or \textbf{b}. Formally, it is the following set: \{\textbf{x }∙ \textbf{a} + \textbf{y} ∙ \textbf{b} | \textbf{x}, \textbf{y} \textbf{Z}; \textbf{x}, \textbf{y} ≥ \textbf{0}\}. Given \textbf{a}, \textbf{b} and two integers \textbf{l} and \textbf{r} (\textbf{l} ≤ \textbf{r}), find how many elements \textbf{e} of the additive class of \textbf{a} and \textbf{b} satisfy the double inequality \textbf{l} ≤ \textbf{e} ≤ \textbf{r}. \InputFile Consists of one or more test cases. The first line contains the number of test cases \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{10 000}). Then follow the test cases themselves. Each test case is given on two lines. The first of these lines contains two positive integers \textbf{a} and \textbf{b} (\textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{10^9}). The second line contains two integers \textbf{l} and \textbf{r} (\textbf{0} ≤ \textbf{l} ≤ \textbf{r} ≤ \textbf{10^18}). \OutputFile For each test case, print the answer on a separate line. The answer for a test case is one integer: the number of elements of the additive class of \textbf{a} and \textbf{b} which belong to \[\textbf{l}, \textbf{r}\]. \Note The example consists of two test cases. In the first test case \textbf{a} = \textbf{3} and \textbf{b} = \textbf{5}. The additive class of these numbers contains the numbers \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}, ... . Two of them belong to the segment \[\textbf{6}, \textbf{8}\]. In the second test case \textbf{a} = \textbf{6} and \textbf{b} = \textbf{4}. Obviously, their additive class contains only even numbers, so no element belongs to the segment \[\textbf{13}, \textbf{13}\].