#arc127f. [arc127_f]±AB

[arc127_f]±AB

问题描述

给定整数 AABBVVMM,其中保证 AABB 是互质的。另外,给定整数 xx,初始时 x=Vx=V

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

  • xx 的值替换为 x+Ax+A

  • xx 的值替换为 xAx-A

  • xx 的值替换为 x+Bx+B

  • xx 的值替换为 xBx-B

在此过程中,必须满足 0xM0 \leq x \leq M

在此条件下,找出 xx 可以取多少个不同的值。

对于每个输入文件,解决 TT 个测试用例。

约束条件

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

输入

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

TT case1case_1 case2case_2 \vdots caseTcase_T

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

AA BB VV MM

输出

对每个测试用例输出答案。


示例输入 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

在第一个测试用例中,xx 可以取四个值:x=0,2,3,5x=0,2,3,5