{"raw_statement":[{"iden":"problem statement","content":"There are $N$ squares indexed $0$ through $(N-1)$ arranged in a line. Snuke is going to mark every square by the following procedure.\n\n1.  Mark square $0$.\n2.  Repeat the following steps i - iii $(N-1)$ times.\n    1.  Initialize a variable $x$ with $(A+D) \\bmod N$, where $A$ is the index of the square marked last time.\n    2.  While square $x$ is marked, repeat replacing $x$ with $(x+1) \\bmod N$.\n    3.  Mark square $x$.\n\nFind the index of the square that Snuke marks for the $K$\\-th time.\nGiven $T$ test cases, find the answer for each of them."},{"iden":"constraints","content":"*   $1\\leq T \\leq 10^5$\n*   $1\\leq K\\leq N \\leq 10^9$\n*   $1\\leq D \\leq 10^9$\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format, where $\\mathrm{test}_i$ denotes the $i$\\-th test case:\n\n$T$\n$\\mathrm{test}_1$\n$\\mathrm{test}_2$\n$\\vdots$\n$\\mathrm{test}_T$\n\nEach test case is given in the following format:\n\n$N$ $D$ $K$"},{"iden":"sample input 1","content":"9\n4 2 1\n4 2 2\n4 2 3\n4 2 4\n5 8 1\n5 8 2\n5 8 3\n5 8 4\n5 8 5"},{"iden":"sample output 1","content":"0\n2\n1\n3\n0\n3\n1\n4\n2\n\nIf $N=4$ and $D=2$, Snuke marks the squares as follows.\n\n1.  Mark square $0$.\n2.  ($1$\\-st iteration) Let $x=(0+2)\\bmod 4=2$. Since square $2$ is not marked, mark it.  \n    ($2$\\-nd iteration) Let $x=(2+2)\\bmod 4=0$. Since square $0$ is marked, let $x=(0+1)\\bmod 4=1$. Since square $1$ is not marked, mark it.  \n    ($3$\\-rd iteration) Let $x=(1+2)\\bmod 4=3$. Since square $3$ is not marked, mark it."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}