Problem Description

有一个二维平面，给定 $length[1], length[2], length[3], length[4]$，画出 4 个正方形区域。

第 $i$ 个区域为 ${(x, y)\ |\ |x| <= length[i], |y| <= length[i]}$。

对于一个整点 $(x, y)$ 其权值为 $(|x|+|y|) * cnt$，其中 $cnt$ 为覆盖该点的区域个数。（点在区域边界上或者在区域内，都称为被区域覆盖）。

现在需要在至少被一个区域覆盖的整点点集中，选出 $k$ 个两两不同的点，使得总权值和最小。

输出最小的权值总和。

Input

第一行一个整数 $T(T \le 100)$ 表示 $T$ 组测试数据。

每组数据有 5 个数字，分别表示 $length[1], length[2], length[3], length[4], k$。满足 $1 \le length[1] < length[2] < length[3] < length[4] \le 10^9, 0 \le k \le 10^{10}$。

数据保证一定能选出 $k$ 个点。

Output

对每组数据输出一行，表示答案。

4
1 2 3 4 1
1 2 3 4 2
1 2 3 4 6
1 5 7 9 12

0
4
20
64

样例解释
对于第一组样例，取 (0,0)；
对于第二组样例，取 (0,0)、(0,1)；
对于第三组样例，取 (0,0)、(0,1)、(1,0)、(-1,0)、(0,-1)、(1,0)、(4,0)；