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.

圣诞老人发现手绘圆圈耗时太久，于是转而求助魔法来完成他的生产配额。

共有三种礼物，其价值分别为 $a$、$b$ 和 $c$。初始时，圣诞老人恰好拥有每种礼物各一个。

给定两个整数 $m$ 和 $k$，分别表示圣诞老人最钟爱的数字以及复制操作的代价。圣诞老人可以任意次数（包括零次）施放以下两类法术：

1. 创造 —— 选择一种类型的礼物，并额外生成一个该类型的礼物。此法术消耗 $x$ 点法力，其中 $x\in \{a,b,c\}$ 是所选类型礼物的价值。
2. 复制 —— 选择一种类型的礼物，并将该类型的所有现有礼物全部复制一份（即数量翻倍）。此法术消耗 $k$ 点法力。

圣诞老人希望执行一系列法术，使得法术后所有礼物的价值总和是 $m$ 的倍数。

请确定圣诞老人达成目标所需的最小法力值。在本题给定的约束条件下，可以证明这样的法术序列一定存在。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例仅有一行，包含五个整数 $a$、$b$、$c$、$m$ 和 $k$（$1\leq a \lt b \lt c \lt m\leq 5\cdot 10^5$，$1\leq k\leq 5\cdot 10^5$）。

保证所有测试用例中 $m$ 的总和不超过 $5\cdot 10^5$。

保证所有测试用例中 $k$ 的总和不超过 $5\cdot 10^5$。

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

对于每个测试用例，输出一个整数——圣诞老人使所有礼物价值之和为 $m$ 的倍数所需的最少法力值。

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$

设 $\ell$ 为礼物价值的列表，$\operatorname{sum}(\ell)$ 表示 $\ell$ 中所有元素的和。

在第一个测试用例中，以下是一种最优的操作序列：

操作

值

操作后的 $\ell$

$\operatorname{sum}(\ell)$

代价

0

—

—

$[1, 2, 3]$

$6$

—

1

创建

$3$

$[1, 2, 3, 3]$

$9$

$3$

2

创建

$3$

$[1, 2, 3, 3, 3]$

$12$

$3$

3

复制

$3$

$[1, 2, 3, 3, 3, 3, 3, 3]$

$21$

$4$

$21=7\cdot 3$

总计：$10$

在第二个测试用例中，最优策略是不执行任何操作，因为 $3+4+5=12$ 已经是 $12$ 的倍数。

在第三个测试用例中，以下是一种最优的操作序列：

操作

值

操作后的 $\ell$

$\operatorname{sum}(\ell)$

代价

0

—

—

$[3, 12, 14]$

$29$

—

1

复制

$12$

$[3, 12, 12, 14]$

$41$

$1$

2

复制

$14$

$[3, 12, 12, 14, 14]$

$55$

$1$

3

创建

$14$

$[3, 12, 12, 14, 14, 14]$

$69$

$14$

4

复制

$3$

$[3, 3, 12, 12, 14, 14, 14]$

$72$

$1$

$72=18\cdot 4$

总计：$17$