{"problem":{"name":"±AB","description":{"content":"Given are integers $A$, $B$, $V$, and $M$, where $A$ and $B$ are guaranteed to be coprime. Additionally, you have an integer $x$. Initially, $x=V$. You can do the following four kinds of operations an","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":8000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc127_f"},"statements":[{"statement_type":"Markdown","content":"Given are integers $A$, $B$, $V$, and $M$, where $A$ and $B$ are guaranteed to be coprime. Additionally, you have an integer $x$. Initially, $x=V$.\nYou can do the following four kinds of operations any number of times in any order.\n\n*   Replace the value of $x$ with $x+A$.\n    \n*   Replace the value of $x$ with $x-A$.\n    \n*   Replace the value of $x$ with $x+B$.\n    \n*   Replace the value of $x$ with $x-B$.\n    \n\nHere, $0 \\leq x \\leq M$ must hold at any moment during this process.\nUnder this condition, find how many different values $x$ can take.\nFor each input file, solve $T$ test cases.\n\n## Constraints\n\n*   $1 \\leq T \\leq 10^5$\n*   $1 \\leq A < B \\leq M \\leq 10^9$\n*   $A$ and $B$ are coprime.\n*   $0 \\leq V \\leq M$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_3$\n\nEach case is in the following format:\n\n$A$ $B$ $V$ $M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc127_f","tags":[],"sample_group":[["5\n3 5 0 5\n1 2 5 10\n5 8 4 9\n10 99 48 106\n500000000 500000001 123456789 900000000","4\n11\n4\n10\n800000002\n\nIn the first case, $x$ can take four values: $x=0,2,3,5$."]],"created_at":"2026-03-03 11:01:14"}}