Problem Visual

Problem Statement

There is a machine consisting of $N$ gears. The cost of the $i~(1 \leq i \leq N)$-th gear is $A_i$. The cost of this machine is defined as the total product (multiplication) of the $N$ gears.

Cherry has some lubricating oil. Using this oil on a gear in the machine lowers the cost of that gear by $K$. However, this oil can only be used on $1$ gear.

Find the minimum possible cost of the machine after using the oil.

Solve $T$ test cases.

Constraints

• $1 \leq T \leq 100$.
• Constraints for each test case
  • $2 \leq N \leq 8$.
  • $1 \leq K \lt 100$.
  • $K \lt A_i \leq 100 \quad (1 \leq i \leq N)$.
• All input values are integers.

Input

The input is given from standard input in the following format.

$T$
${\rm Testcase}_1$
$\vdots$
${\rm Testcase}_T$

Each test case is given in the following format.

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$

Output

The output consists of $T$ lines. On the $t~(1 \leq t \leq T)$-th line, print the answer to the $t$-th test case as an integer.

Do not forget the newline at the end.

Sample

3
3 5
10 20 30
6 99
100 100 100 100 100 100
2 1
3 23

3000
10000000000
46