CareerCup

hello all can some1 help how to approach this prob:
After travelling lot around the roads of Britain, our friend Sherlock has realised the vastness of Jim Moriarity's Powers.
He realises that his wisdom alone won't be sufficient in his march to victory.
He therefore visits the "Forest of Magic". As the name suggests, the forest is magical in the sense that it has magical portals which release "Magical aura" when activated.
The amount of Magical Aura is calculated in terms of "Mana Points".
On entering the forest he sees 'n' number of portals in front of him numbered from '0' to 'n-1' arranged in a straight line.
Each portal has a value written over it. He sees that the first and the last portals are damaged and cannot be activated (remain unactivated).

He can perform the following operations repeatedly to gain Magical Aura :
1. He can activate a portal 'x' (obviously not the first and the last one).
2. Let 'l' be the nearest unactivated portal to the left of 'x' and 'r' be the nearest unactivated portal to the right of 'x'.
3. On activating the portal 'x' he gains Mana points equal to the product of value of written over 'l' and the value written over 'r'.
4. A portal once activated cannot be activated again.

He stops when the above process cannot be continued anymore.
Note that 'nearest' is with respect to the portal currently being activated.

Now Sherlock is thinking what is the maximum amount of Magical Aura (Mana points) he can First line contains no of testcases 't'.
Next 't' testcases follow, first line of each is an integer 'n', representing number of portals inside the forest.
Next line contains 'n' space seperated integers which are the values written over the corresponding n portals.

Ouptut :
Output 'n' lines each having one integer denoting the maximum amount of Mana points he can gain for that particular testcase.

Constraints :
1 <= t <= 500
3 <= n <= 80
1 <= Value written over each portal <= 1000

Sample Input :
1
4
1 2 3 4

Sample Output :
12

Explanation :
We have only 2 choices :
1. Activate portal numbered 1 first, and portal numbered 2 next. The total Mana points are 1 * 3 + 1 * 4 = 7.
2. Activate portal numbered 2 first, and portal numbered 1 next. The total Mana points are 2 * 4 + 1 * 4 = 12.

So the answer is 12.gain in this process.??
plz help how to approch this??
Help him find this.