Fields X82108

In the Middle Ages, many villages practiced agriculture using the open-field system: each field was divided into many narrow strips of land, each cultivated by a different family.

The government of Utopia has decided to reform agriculture and cultivate each field using modern equipment. To compensate the families of each village, the government has agreed to make a cash payment to each village. The amount of the cash payment is calculated using the procedure described below.

For simplicity, assume that the strips of land are all vertical. Given a field with n strips of land, let l₀,l₁,…,l_n be the lengths of their borders, where l_i−1 is the length of the left border of strip i, and l_i is the length of the right border. Note that the right border of strip i−1 is also the left border of strip i.

When merging two adjoining strips of land i−1 and i, the cash payment is l_i−1× l_i× l_i+1, i.e. the product of the lengths of the three borders of i−1 and i (including the common border that separates them). After merging the two strips of land, they become a single strip whose borders have lengths l_i−1 and l_i+1.

Your goal is to help the villagers maximize the compensatory cash payment.

Input

The input starts with the number of test cases T ≤ 100. For each test case, there is an intenger n ≤ 100 that represents the number of strips of land in a given field. On the next line, there are n+1 numbers l₀,l₁,…,l_n describing the lengths of the borders.

Output

For each test case, print the maximum cash payment C for the given field on a separate line.

In the first example, there are three strips of land 1, 2 and 3. There are two ways to merge the strips: first merge 1 and 2, and then merge the resulting strip with 3, or first merge 2 and 3, and then merge the resulting strip with 1. The cash payment for the first case is 1× 4 × 3 + 1× 3× 2 = 20, while the cash payment for the second case is 4× 3× 2 + 1× 4× 2 = 32. Hence the second case is optimal.

In the second example, there are four strips of land. The maximum cash payment is achieved by merging 2 with 3, then merging the result with 1, and finally merging the result with 4, resulting in a cash payment of 3× 2× 3 + 4× 3× 3 + 4× 3× 4 = 102.