Background

Special for beginners, ^_^

Description

现在有个带六个参数的函数， $\lfloor \frac{ e+\sum\limits_{i=1}^{n} n(a+b+cd)}{f}\rfloor$， 给出六个数，请合理分配这六个数分别给a~f，当然每个数只能用一次，使得前面的那个带六个参数的函数最大。

Format

Input

第一行输入一个正整数T($1\leq T\leq 10^6$)，表示有T组测试数据。 对于每组测试数据： 第一行输入六个正整数a,b,c,d,e,f($1\leq a,b,c,d,e,f\leq 10^3$)。 第二行输入一个正整数n($1\leq n\leq 10^4$)。

Output

对于每组测试数据输出一行一个整数，表示答案。

Samples

3
1 1 1 1 1 1
1
1 2 3 4 5 6
2
6 5 4 3 2 1
3

4
150
335

Limitation

1s, 1024KiB for each test case.