Şehmettin Ltd. Co. is in the interstellar titanium transportation business. They rent spaceships that can carry \(\mathbf{K}\ \mathbf{m}^3\) of titanium. The company only produces rectangular prism shaped titanium blocks of size \(\mathbf{X \times Y \times Z}\). So, to transport titanium, you may need to cut the titanium block multiple times.

In one move you can cut the titanium block either from width, length or height into 2 titanium blocks. The dimensions of newly created titanium blocks must be integers (e.g. a \([5 \times 6 \times 7]\) block might be cut into \([5 \times 2 \times 7]\) and \([5 \times 4 \times 7]\) sized 2 blocks, but it cannot be cut into \([5 \times 1.5 \times 7]\) and \([5 \times 4.5 \times 7]\) sized 2 blocks). However, titanium is a hard metal to cut; therefore, the cost of cutting the titanium block is the square of cut surface area (e.g. if a \([5 \times 6 \times 7]\) sized block is cut into \([5 \times 2 \times 7]\) and \([5 \times 4 \times 7]\) sized 2 blocks its cutting cost will be \((5 \times 7)^2 = 1225\)).

Your job as an employee of Şehmettin Ltd. Co. is to find the minimum total cost of cutting titanium blocks for given \(\mathbf{X}\), \(\mathbf{Y}\), \(\mathbf{Z}\) and \(\mathbf{K}\) values.

The ship can transport multiple titanium blocks but the total volume of the blocks should be \(\mathbf{K}\).(e.g. if the initial block is \([2 \times 2 \times 2]\) sized and if \(\mathbf{K}\) is 5, the ship can either transport 1 \([2 \times 2 \times 1]\) block with a \([1 \times 1 \times 1]\) block or it can transport 5 \([1 \times 1 \times 1]\) blocks)

The remaining \((\mathbf{X \times Y \times Z - K})\) \(\mathbf{m}^3\) of titanium does not necessarily form a single rectangular prism.

Input

• The first line contains \(\mathbf{1}\) integer, \(\mathbf{T}\):
  • \(1 \leq \mathbf{T} \leq 10^4\), The number of test cases.
• Each one of the \(\mathbf{T}\) consecutive lines contains \(\mathbf{4}\) integers, \(\mathbf{X,\ Y,\ Z,\ K}\):
  • \(1 \leq \mathbf{X,\ Y,\ Z} \leq 10\), dimensions of the titanium block.
  • \(0 \leq \mathbf{K} \leq min(50,\ \mathbf{X \times Y \times Z})\), how many \(\mathbf{m}^3\) of titanium the spaceship can carry.

Output

For each \(\mathbf{X,\ Y,\ Z}\) and \(\mathbf{K}\), print the minimum total cost needed to cut the titanium block, in order to make it possible to transport exactly \(\mathbf{K}\) \(\mathbf{m}^3\) of titanium.

Example

Input:

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

Output:

21
16
10

Explanation:

First Case:

• The block whose dimension is 2 2 2 can be cut into two pieces. (2 2 2 -> 1 2 2 and 1 2 2). The cost of that move will be 16.
• The block whose dimension is 1 2 2 can be cut into two pieces. (1 2 2 -> 1 1 2 and 1 1 2). The cost of that move will be 4.
• Then, the block whose dimension is 1 1 2 can be cut into two pieces. (1 1 2 -> 1 1 1 and 1 1 1). The cost of that move will be 1.
• To solve this optimally we will use a block of 1 2 2 with a block of 1 1 1.(\((1 \times 2 \times 2 + 1 \times 1 \times 1=5=\mathbf{K})\))

The total cost will be 21.

Third Case:

• The block whose dimension is 1 3 3 can be cut like following: 1 3 3 -> 1 3 1 and 1 3 2. The cost of this move will be 9.
• The block whose dimension is 1 3 1 can be cut like following: 1 3 1 -> 1 1 1 and 1 2 1. The cost of this move will be 1 .
• To solve this we will need a block of 1 1 1.(\((1 \times 1 \times 1=1=\mathbf{K})\))

In the end, we can acquire 1 1 1 cube. The total cost will be 10.