题目描述

整数 $A,B,V,M$ が与えられます． ここで，$A$ と $B$ は互いに素であることが保証されます． また，あなたは整数 $x$ を持っています． 最初，$x=V$ です．

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

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

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

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

一つの入力ファイルにつき，$T$ 個のテストケースを解いてください．

输入格式

入力は以下の形式で標準入力から与えられる．

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

各ケースは以下の形式で与えられる．

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

输出格式

各ケースについて答えを出力せよ．

题目大意

给定整数 $A,B,V,M$，其中 $A,B$ 保证互质。另外，还有一个整数 $x$，初始化为 $x=V$。

您可以按任意顺序执行以下四种操作，次数不限。

将 $x$ 的值修改为 $x+A$

将 $x$ 的值修改为 $x-A$

将 $x$ 的值修改为 $x+B$

将 $x$ 的值修改为 $x-B$

在操作过程中，$0\le x \le M$ 必须在任意时刻成立。

问在这种情况下，$x$ 可以取多少不同的值。

多组数据。

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

4
11
4
10
800000002

提示

制約

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

Sample Explanation 1

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