Additive Class#7315
Sign in

Additive Class

1 second
128 megabytes
Very hard

Determine how many elements of the additive class of numbers and belong to the interval [l; r].

The additive class of positive integers and is the set of numbers that can be represented as a sum of zero or more terms, each equal to either or . Formally:

S(a, b) = \{\, x \cdot a + y \cdot b \mid x, y \in \mathbb{Z}, \; x \ge 0, \; y \ge 0 \}

You are given numbers , , and two integers and (l \leq r). Find the number of elements e \in S(a, b) that satisfy the inequality l \le e \le r.

Input

The first line contains an integer (1 \le t \le 10000) — the number of test cases.

Then the descriptions of the test cases follow. Each test case consists of two lines:

  • the first line contains two positive integers and (1 \le a, b \le 10^9);

  • the second line contains two integers and (0 \le l \le r \le 10^{18}).

Output

For each test case, print one integer — the number of elements of the additive class S(a, b) that belong to the interval [l; r].

Examples

Example 1

Loading
Loading