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. 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< b< c< 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). 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). 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: In the second test case, it is optimal to not perform any operat