H. Create or Duplicate
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Santa realized that hand-drawing circles takes too long, so he has turned to magic to meet his production quotas.

There are three types of presents with distinct values $$$a$$$, $$$b$$$, and $$$c$$$. Initially, Santa has exactly one present of each type.

You are given two integers $$$m$$$ and $$$k$$$, representing Santa's favorite number and the cost of duplication, respectively. Santa can cast the following two types of spells any number of times (possibly zero):

  1. Create — Choose a type of present and create one additional present of that type. This spell costs $$$x$$$ mana, where $$$x\in \{a,b,c\}$$$ is the value of the chosen type.
  2. Duplicate — Choose a type of present and duplicate all presents of that type. This spell costs $$$k$$$ mana.

Santa wants to perform a sequence of spells such that the sum of the values of all presents is a multiple of $$$m$$$ after the spells.

Determine the minimum amount of mana Santa needs to achieve this. It can be shown that, under the given constraints, such a sequence of spells always exists.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The only line of each test case contains five integers $$$a$$$, $$$b$$$, $$$c$$$, $$$m$$$, and $$$k$$$ ($$$1\leq a \lt b \lt c \lt m\leq 5\cdot 10^5$$$, $$$1\leq k\leq 5\cdot 10^5$$$).

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.

Output

For each test case, output a single integer — the minimum amount of mana Santa needs to make the sum of the values of all presents a multiple of $$$m$$$.

Example
Input
7
1 2 3 21 4
3 4 5 12 34
3 12 14 18 1
6 7 8 10 3
100 103 282 488 221
307 2000 5096 12018 5764
194093 292793 395323 475619 490151
Output
10
0
17
9
1227
35116
7050242
Note

Let $$$\ell$$$ be the list of values of presents and $$$\operatorname{sum}(\ell)$$$ be the sum of all elements in $$$\ell$$$.

In the first test case, below is an optimal sequence of operations:

#OperationValue$$$\ell$$$ after operation$$$\operatorname{sum}(\ell)$$$Cost
0——$$$[1, 2, 3]$$$$$$6$$$—
1Create$$$3$$$$$$[1, 2, 3, 3]$$$$$$9$$$$$$3$$$
2Create$$$3$$$$$$[1, 2, 3, 3, 3]$$$$$$12$$$$$$3$$$
3Duplicate$$$3$$$$$$[1, 2, 3, 3, 3, 3, 3, 3]$$$$$$21$$$$$$4$$$
$$$21=7\cdot 3$$$Total: $$$10$$$

In the second test case, it is optimal to not perform any operations because $$$3+4+5=12$$$ is already a multiple of $$$12$$$.

In the third test case, below is an optimal sequence of operations:

#OperationValue$$$\ell$$$ after operation$$$\operatorname{sum}(\ell)$$$Cost
0——$$$[3, 12, 14]$$$$$$29$$$—
1Duplicate$$$12$$$$$$[3, 12, 12, 14]$$$$$$41$$$$$$1$$$
2Duplicate$$$14$$$$$$[3, 12, 12, 14, 14]$$$$$$55$$$$$$1$$$
3Create$$$14$$$$$$[3, 12, 12, 14, 14, 14]$$$$$$69$$$$$$14$$$
4Duplicate$$$3$$$$$$[3, 3, 12, 12, 14, 14, 14]$$$$$$72$$$$$$1$$$
$$$72=18\cdot 4$$$Total: $$$17$$$