分数: 1000 点
问题陈述
给定的是整数 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_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
在第一种情况下, x 可以采用四个值: x=0,2,3,5.