Problem Statement

Given are integers $A$, $B$, $V$, and $M$, where $A$ and $B$ are guaranteed to be coprime. Additionally, you have an integer $x$. Initially, $x=V$.

You can do the following four kinds of operations any number of times in any order.

• Replace the value of $x$ with $x+A$.

• Replace the value of $x$ with $x-A$.

• Replace the value of $x$ with $x+B$.

• Replace the value of $x$ with $x-B$.

Here, $0 \\leq x \\leq M$ must hold at any moment during this process.

Under this condition, find how many different values $x$ can take.

For each input file, solve $T$ test cases.

Constraints

• $1 \\leq T \\leq 10^5$
• $1 \\leq A < B \\leq M \\leq 10^9$
• $A$ and $B$ are coprime.
• $0 \\leq V \\leq M$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$T$ $case_1$ $case_2$ $\\vdots$ $case_3$

Each case is in the following format:

$A$ $B$ $V$ $M$

Output

Print the answer for each case.

Sample Input 1

5
3 5 0 5
1 2 5 10
5 8 4 9
10 99 48 106
500000000 500000001 123456789 900000000

Sample Output 1

4
11
4
10
800000002

In the first case, $x$ can take four values: $x=0,2,3,5$.