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.