A - Ax+By Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 4 点

問題文

以下の条件を満たす整数の組 x,y がいくつあるかを求めて下さい。

  • 0 \leq x, y \leq N
  • Ax+By は C の倍数

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

3 点の部分点のデータでは以下の条件を満たします。

  • T = 1
  • 1 \leq N \leq 1000
  • 1 \leq A,B,C \leq 10^9

満点のデータでは以下の条件を満たし、上記とは別に 1 点が与えられます。（満点解法はとても難しいので、一旦飛ばすことをおすすめします。）

  • 1 \leq T \leq 10^5
  • 1 \leq N \leq 10^9
  • 1 \leq A,B,C \leq 10^9

入力

入力は以下の形式で標準入力から与えられます。

T
case_1
\vdots
case_T

各テストケースは以下の形式で与えられます。

N A B C

出力

T 行出力して下さい。 i 行目には、case_i に対する答えを出力して下さい。

入力例 1

1
2 3 4 5

出力例 1

2

入力例 2

1
1000 314159265 271828182 2023

出力例 2

496