Additive Class

In this problem, you have to find how many elements of the additive class of a and b belong to [l, r].

An additive class of positive integers a and b is the set of numbers representable as a sum of zero or more numbers each of which is either a or b. Formally, it is the following set: {x ∙ a + y ∙ b | x, y Z; x, y ≥ 0}.

Given a, b and two integers l and r (l ≤ r), find how many elements e of the additive class of a and b satisfy the double inequality l ≤ e ≤ r.

Input

Consists of one or more test cases. The first line contains the number of test cases t (1 ≤ t ≤ 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 a and b (1 ≤ a, b ≤ 10^9). The second line contains two integers l and r (0 ≤ l ≤ r ≤ 10^18).

Output

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 a and b which belong to [l, r].

Examples

Note

The example consists of two test cases.

In the first test case a = 3 and b = 5. The additive class of these numbers contains the numbers 0, 3, 5, 6 = 3 + 3, 8 = 3 + 5, 9 = 3 + 3 + 3, ... . Two of them belong to the segment [6, 8].

In the second test case a = 6 and b = 4. Obviously, their additive class contains only even numbers, so no element belongs to the segment [13, 13].