题目描述

给定整数 $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_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

输出

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$
• 输入的所有值均为整数。

样例解释 1

对于第 $1$ 个测试用例，$x$ 可能为 $0,2,3,5$，共 $4$ 种不同的值。

由 ChatGPT 4.1 翻译