{"raw_statement":[{"iden":"problem statement","content":"You are given positive integers $A$, $B$, $X$, $Y$, and $N$. Here, the following is guaranteed:\n\n*   $A<B$\n*   $\\gcd(A,B)=1$\n*   $1 \\leq N \\leq A+B-1$\n\nFor an integer $n$, define $f(n)$ as follows:\n\n*   You start with an integer $x=0$. $f(n)$ is the minimum total cost to achieve $x=n$ by repeatedly performing the following operations.\n    *   Replace the value of $x$ with $x+A$. The cost of this operation is $X$.\n    *   Replace the value of $x$ with $x-A$. The cost of this operation is $X$.\n    *   Replace the value of $x$ with $x+B$. The cost of this operation is $Y$.\n    *   Replace the value of $x$ with $x-B$. The cost of this operation is $Y$.\n\nIt can be proved from the constraints on $A$ and $B$ that $f(n)$ is defined for any integer $n$.\nFind the value of $\\sum_{1 \\leq n \\leq N} f(n)$, modulo $998244353$.\nThere are $T$ test cases for each input."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 1000$\n*   $1 \\leq A<B \\leq 10^9$\n*   $\\gcd(A,B)=1$\n*   $1 \\leq X,Y \\leq 10^9$\n*   $1 \\leq N \\leq A+B-1$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach test case is given in the following format:\n\n$A$ $B$ $X$ $Y$ $N$"},{"iden":"sample input 1","content":"4\n1 2 1 1 2\n3 5 2 4 6\n79 85 72 95 4\n80980429 110892168 22712439 520643153 66132787"},{"iden":"sample output 1","content":"2\n34\n18111\n785776602\n\nIn the first test case, $f(1)=1$ and $f(2)=1$.\nIn the second test case, $f(1)=8$, $f(2)=6$, $f(3)=2$, $f(4)=10$, $f(5)=4$, and $f(6)=4$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}