{"raw_statement":[{"iden":"problem statement","content":"There is a sequence $X=(X_0, X_1, \\ldots)$ defined by the following recurrence relation.\n$X_i = \\left{ \\begin{array}{ll} S & (i = 0)\\\\ (A X_{i-1}+B) \\bmod P & (i \\geq 1) \\end{array} \\right.$\nDetermine whether there is an $i$ such that $X_i=G$. If it exists, find the smallest such $i$.  \nHere, $x \\bmod y$ denotes the remainder when $x$ is divided by $y$ (the least non-negative residue).\nYou are given $T$ test cases for each input file."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 100$\n*   $2 \\leq P \\leq 10^9$\n*   $P$ is a prime.\n*   $0\\leq A,B,S,G < P$\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach test case is in the following format:\n\n$P$ $A$ $B$ $S$ $G$"},{"iden":"sample input 1","content":"3\n5 2 1 1 0\n5 2 2 3 0\n11 1 1 0 10"},{"iden":"sample output 1","content":"3\n-1\n10\n\nFor the first test case, we have $X=(1,3,2,0,\\ldots)$, so the smallest $i$ such that $X_i=0$ is $3$.  \nFor the second test case, we have $X=(3,3,3,3,\\ldots)$, so there is no $i$ such that $X_i=0$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}