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):

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

#	Operation	Value	$$$\ell$$$ after operation	$$$\operatorname{sum}(\ell)$$$	Cost
0	—	—	$$$[1, 2, 3]$$$	$$$6$$$	—
1	Create	$$$3$$$	$$$[1, 2, 3, 3]$$$	$$$9$$$	$$$3$$$
2	Create	$$$3$$$	$$$[1, 2, 3, 3, 3]$$$	$$$12$$$	$$$3$$$
3	Duplicate	$$$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:

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

Create or Duplicate

Examples