Contest Duration: - (local time) (120 minutes) Back to Home
F - ±AB /

Time Limit: 8 sec / Memory Limit: 1024 MB

### 問題文

あなたは，以下の 4 種類の操作を好きな順序で好きな回数繰り返すことができます．

• x の値を，x+A で置き換える．

• x の値を，x-A で置き換える．

• x の値を，x+B で置き換える．

• x の値を，x-B で置き換える．

ただし，操作のどの瞬間においても，0 \leq x \leq M が成立している必要があります．

この条件の元で，x がとりうる値が何種類あるかを求めてください．

### 制約

• 1 \leq T \leq 10^5
• 1 \leq A < B \leq M \leq 10^9
• AB は互いに素である．
• 0 \leq V \leq M
• 入力される値はすべて整数である．

### 入力

T
case_1
case_2
\vdots
case_3


A B V M


### 入力例 1

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


### 出力例 1

4
11
4
10
800000002


1 つ目のテストケースでは，x=0,2,3,54 通りの値が考えられます．

Score : 1000 points

### 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.