{"raw_statement":[{"iden":"statement","content":"Given two positive integers $n$ and $k$, you can perform the following two types of operations any number of times (including zero times):\n\n- Choose an integer $x$ which satisfies $0 \\leq x < k$, and change $n$ into $k\\cdot n+x$. It will cost you $a$ coins to perform this operation once. The integer $x$ you choose each time can be different.\n- Change $n$ into $\\lfloor \\frac{n}{k} \\rfloor$. It will cost you $b$ coins to perform this operation once. Note that $\\lfloor \\frac{n}{k} \\rfloor$ is the largest integer which is less than or equal to $\\frac{n}{k}$.\n\nGiven a positive integer $m$, calculate the minimum number of coins needed to change $n$ into a multiple of $m$. Please note that $0$ is a multiple of any positive integer.\n"},{"iden":"input","content":"There are multiple test cases. The first line of the input contains an integer $T$ ($1\\leq T\\leq 10^5$) indicating the number of test cases. For each test case:\n\nThe first line contains five integers $n$, $k$, $m$, $a$, $b$ ($1\\leq n\\leq 10^{18}$, $1\\leq k, m, a, b\\leq 10^9$)."},{"iden":"output","content":"For each test case output one line containing one integer, indicating the minimum number of coins needed to change $n$ into a multiple of $m$. If this goal cannot be achieved, output $-1$ instead."},{"iden":"note","content":"For the first sample test case, initially $n=101$. The optimal steps are shown as follows:\n\n- Firstly, perform the second type of operation once. Change $n$ into $\\lfloor \\frac{n}{4} \\rfloor=25$. This step costs $5$ coins.\n- Then, perform the first type of operation once. Choose $x = 3$ and change $n$ into $4\\cdot n+3=103$. This step costs $3$ coins.\n- Then, perform the first type of operation once. Choose $x = 2$ and change $n$ into $4\\cdot n+2=414$. This step costs $3$ coins.\n- As $414=2 \\times 207$, $n$ is a multiple of $m$. The total cost is $5+3+3=11$ coins.\n\nFor the second sample test case, perform the second type of operation twice will change $n$ into $0$. The total cost is $1 + 1 = 2$ coins.\n\nFor the third sample test case, as $n = 114 = 6 \\times 19$ is already a multiple of $m$, no operation is needed. The total cost is $0$ coins."}],"translated_statement":null,"sample_group":[["4\n101 4 207 3 5\n8 3 16 100 1\n114 514 19 19 810\n1 1 3 1 1","11\n2\n0\n-1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}