{"problem":{"name":"Simple Math 3","description":{"content":"In this problem, you will be given $T$ test cases for each input. Given integers $A$, $B$, $C$, and $D$, find the number of positive integers $i$ satisfying the following condition: *   None of the i","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc111_e"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $1 \\leq T \\leq 10{,}000$\n*   $1 \\leq A < D$\n*   $0 \\leq B < C < D$\n*   $2 \\leq D \\leq 10^8$\n\n## Input\n\nInput 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc111_e","tags":[],"sample_group":[["2\n3 1 2 5\n99 101 103 105","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*   $:$"]],"created_at":"2026-03-03 11:01:14"}}