题目描述

给定四个正整数$a,b,c,d$。你可以进行至多$k$次操作，每次操作可以从 $a,b,c,d$ 中选择一个数，令这个数加 $1$，求操作后这四个正整数的乘积 $a\times b\times c\times d$ 的最大值。

输入描述

输入包含多组测试数据。

输入第一行包含一个正整数$T(1\le T\le 100)$，表示测试数据组数。

接下来$T$行，每行描述了一组测试数据，包含 $a,b,c,d,k(1\le a,b,c,d,k\le 20)$五个整数。

输出描述

输出包含 $T$ 行。

对于每组测试数据输出一行一个整数，表示操作后这四个正整数的乘积 $a\times b\times c\times d$ 的最大值。

样例

输入

2
1 2 3 4 2
1 2 1 2 3

输出

72
24

样例解释

对于样例第一组测试数据，乘积最大为 $72$，此时操作后四个数可以分别为$2，3，3，4$。

对于样例第二组测试数据，乘积最大为 $24$，此时操作后四个数可以分别为$2，2，2，3$。