← 返回题目列表

AtCoder · arc127_f

F. 正负AB

中文机器翻译题面 查看原题

分数: 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.