问题描述

给定整数 $A$、$B$、$V$ 和 $M$，其中保证 $A$ 和 $B$ 是互质的。另外，给定整数 $x$，初始时 $x=V$。

你可以任意顺序，任意次数地进行以下四种操作：

• 将 $x$ 的值替换为 $x+A$。

• 将 $x$ 的值替换为 $x-A$。

• 将 $x$ 的值替换为 $x+B$。

• 将 $x$ 的值替换为 $x-B$。

在此过程中，必须满足 $0 \leq x \leq M$。

在此条件下，找出 $x$ 可以取多少个不同的值。

对于每个输入文件，解决 $T$ 个测试用例。

约束条件

• $1 \leq T \leq 10^5$
• $1 \leq A < B \leq M \leq 10^9$
• $A$ 和 $B$ 是互质的。
• $0 \leq V \leq M$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

每个测试用例的格式如下：

$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

在第一个测试用例中，$x$ 可以取四个值：$x=0,2,3,5$。