AT_abc443_g [ABC443G] Another Mod of Linear Problem

You are given integers $ N,M,A,B $ . Define an integer sequence $ X=(X_0,X_1,\ldots,X_{N-1}) $ as $ \displaystyle X_k = (Ak+B) \bmod M $ . Find the number of integers $ k $ satisfying $ 0 \le k < N $ and $ X_k > k $ . You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $ $ M $ $ A $ $ B $

Output the answers for the test cases in order, separated by newlines.

### Sample Explanation 1 Consider the first test case. - When $ k=0 $ : $ X_0=(4\times 0+3)\bmod 6=3 $ , so $ X_k>k $ holds. - When $ k=1 $ : $ X_1=(4\times 1+3)\bmod 6=1 $ , so $ X_k>k $ does not hold. - When $ k=2 $ : $ X_2=(4\times 2+3)\bmod 6=5 $ , so $ X_k>k $ holds. - When $ k=3 $ : $ X_3=(4\times 3+3)\bmod 6=3 $ , so $ X_k>k $ does not hold. From the above, the integers $ k $ satisfying $ 0 \le k < 4 $ and $ X_k>k $ are $ k=0,2 $ , which is two integers. Thus, output $ 2 $ on the first line. ### Constraints - $ 1\le T\le 3\times 10^5 $ - $ 1\le N \le M\le 10^9 $ - $ 0\le A,B < M $ - All input values are integers.