{"raw_statement":[{"iden":"problem statement","content":"In this problem, you will be given $T$ test cases for each input.\nGiven integers $A$, $B$, $C$, and $D$, find the number of positive integers $i$ satisfying the following condition:\n\n*   None of the integers between $A + B \\times i$ and $A + C \\times i$ (inclusive) is a multiple of $D$.\n\nWe can prove from the constraints that the count is finite."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 10{,}000$\n*   $1 \\leq A < D$\n*   $0 \\leq B < C < D$\n*   $2 \\leq D \\leq 10^8$"},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$T$\n$A_1$ $B_1$ $C_1$ $D_1$\n$:$\n$A_T$ $B_T$ $C_T$ $D_T$"},{"iden":"sample input 1","content":"2\n3 1 2 5\n99 101 103 105"},{"iden":"sample output 1","content":"1\n25\n\nThe pairs $(A + B \\times i, A + C \\times i)$ for the first case are listed below. We can see that only $i = 3$ satisfies the condition.\n\n*   $i = 1: (4, 5)$\n*   $i = 2: (5, 7)$\n*   $i = 3: (6, 9)$\n*   $i = 4: (7, 11)$\n*   $i = 5: (8, 13)$\n*   $:$"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}