There is a regular polygon with (n) sides ((n \ge 3)). The vertices are indexed as (1,2,\ldots,n) in clockwise order. On each vertex (i), the pink soldiers have written a positive integer (a_i). With this regular polygon, you will play a game defined as follows. Initially, your score is (0). Then, you perform the following operation any number of times to increase your score. Select (3) different vertices (i), (j), (k) that you have not chosen before, and draw the triangle formed by the three vertices. Then, your score increases by (a_i \cdot a_j \cdot a_k). However, you can not perform this operation if the triangle shares a positive common area with any of the triangles drawn previously. Then, your score increases by (a_i \cdot a_j \cdot a_k). However, you can not perform this operation if the triangle shares a positive common area with any of the triangles drawn previously. Your objective is to maximize the score. Please find the maximum score you can get from this game. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test case contains a single integer (n) — the number of vertices ((3 \le n \le 400)). The second line of each test case contains (a_1,a_2,\ldots,a_n) — the integers written on vertices ((1 \le a_i \le 1000)). It is guaranteed that the sum of (n^3) over all test cases does not exceed (400^3). For each test case, output the maximum score you can get on a separate line. On the first test case, you can draw only one triangle. The maximum score (6) is found by drawing the triangle with (i=1), (j=2), (k=3). On the second test case, you can draw only one triangle. The maximum score (24) is found by drawing the triangle with (i=1), (j=3), (k=4). On the third test case, you can draw two triangles. There is a