AT_abc443_g [ABC443G] Another Mod of Linear Problem

整数 $ N,M,A,B $ が与えられます。 整数列 $ X=(X_0,X_1,\ldots,X_{N-1}) $ を $ \displaystyle X_k = (Ak+B) \bmod M $ として定義します。 $ X_k > k $ を満たす $ 0 $ 以上 $ N $ 未満の整数 $ k $ の個数を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ A $ $ B $

各テストケースに対する答えを順に改行区切りで出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて考えます。 - $ k=0 $ のとき： $ X_0=(4\times 0+3)\bmod 6=3 $ なので、 $ X_k>k $ が成立します。 - $ k=1 $ のとき： $ X_1=(4\times 1+3)\bmod 6=1 $ なので、 $ X_k>k $ は成立しません。 - $ k=2 $ のとき： $ X_2=(4\times 2+3)\bmod 6=5 $ なので、 $ X_k>k $ が成立します。 - $ k=3 $ のとき： $ X_3=(4\times 3+3)\bmod 6=3 $ なので、 $ X_k>k $ は成立しません。 以上より、 $ X_k>k $ が成立する $ 0 $ 以上 $ 4 $ 未満の整数 $ k $ は $ k=0,2 $ の $ 2 $ 個です。したがって、 $ 1 $ 行目には $ 2 $ を出力してください。 ### Constraints - $ 1\le T\le 3\times 10^5 $ - $ 1\le N \le M\le 10^9 $ - $ 0\le A,B < M $ - 入力される値は全て整数