AT_editor_update_test_a Ax+By

以下の条件を満たす整数の組 $ x,y $ がいくつあるかを求めて下さい。 - $ 0 \leq x, y \leq N $ - $ Ax+By $ は $ C $ の倍数 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられます。 > $ T $ $ case_1 $ $ \vdots $ $ case_T $ 各テストケースは以下の形式で与えられます。 > $ N $ $ A $ $ B $ $ C $

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

### Constraints $ 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 $