201275: [AtCoder]ARC127 F - ±AB

Memory Limit:1024 MB Time Limit:8 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $1000$ points

Problem Statement

Given are integers $A$, $B$, $V$, and $M$, where $A$ and $B$ are guaranteed to be coprime. Additionally, you have an integer $x$. Initially, $x=V$.

You can do the following four kinds of operations any number of times in any order.

  • Replace the value of $x$ with $x+A$.

  • Replace the value of $x$ with $x-A$.

  • Replace the value of $x$ with $x+B$.

  • Replace the value of $x$ with $x-B$.

Here, $0 \leq x \leq M$ must hold at any moment during this process.

Under this condition, find how many different values $x$ can take.

For each input file, solve $T$ test cases.

Constraints

  • $1 \leq T \leq 10^5$
  • $1 \leq A < B \leq M \leq 10^9$
  • $A$ and $B$ are coprime.
  • $0 \leq V \leq M$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$T$
$case_1$
$case_2$
$\vdots$
$case_3$

Each case is in the following format:

$A$ $B$ $V$ $M$

Output

Print the answer for each case.


Sample Input 1

5
3 5 0 5
1 2 5 10
5 8 4 9
10 99 48 106
500000000 500000001 123456789 900000000

Sample Output 1

4
11
4
10
800000002

In the first case, $x$ can take four values: $x=0,2,3,5$.

Input

题意翻译

给定整数 $A,B,V,M$,其中 $A,B$ 保证互质。另外,还有一个整数 $x$,初始化为 $x=V$。 您可以按任意顺序执行以下四种操作,次数不限。 将 $x$ 的值修改为 $x+A$ 将 $x$ 的值修改为 $x-A$ 将 $x$ 的值修改为 $x+B$ 将 $x$ 的值修改为 $x-B$ 在操作过程中,$0\le x \le M$ 必须在任意时刻成立。 问在这种情况下,$x$ 可以取多少不同的值。 多组数据。

加入题单

上一题 下一题 算法标签: