Problem Description

Let's define the sum of all digits in $x$ as $g(x)$. For example, $g(123) = 1 + 2 + 3 = 6$. Give you a function:
$$
f(x) = Ax^2g(x) + Bx^2 + Cxg^2(x) + Dxg(x)
$$
Find the minimum value of $f(x)$, where $x$ is an integer and $1 \leq x \leq N$.

Input

This problem contains multiple test cases.

The first line of the input contains an integer $T (1 \leq T \leq 10^4)$, representing the number of test cases.

Each of the next $T$ lines contains five integers $A, B, C, D, N (0 \leq |A| \leq 10^3, 0 \leq |B|, |C|, |D| \leq 10^6, 1 \leq N \leq 10^6)$ indicating a test case.

Output

For each test case output an integer, denoting the answer.

2
1 2 3 4 100
4 3 2 1 100

10
10