[ARC127F] ±AB

给定整数 $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$ 可以取多少不同的值。 多组数据。

[problemUrl]: https://atcoder.jp/contests/arc127/tasks/arc127_f 整数 $ 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_3 $ 各ケースは以下の形式で与えられる． > $ A $ $ B $ $ V $ $ M $

各ケースについて答えを出力せよ．

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 $ - 入力される値はすべて整数である． ### Sample Explanation 1 $ 1 $ つ目のテストケースでは，$ x=0,2,3,5 $ の $ 4 $ 通りの値が考えられます．