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$.

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)$Cost0——$[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)$Cost0——$[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$