Mixtures

Hermione is attending the Magic Potion's Class in Hogwarts. She has ‘N’ potions in front of her lying in a row. Her task is to combine these potions into 1. To do so, she can pick any two adjacent potions of color ‘A’, ‘B’ and mix them to form another potion of color ‘C’=(‘A’ + ‘B’)%100, which will then replace ‘A’ and ‘B’ in the row (Two potions combine to form one potion). But when a new potion is formed, it produces smoke of value ‘A’ * ‘B’. Hermione needs your help to minimize the smoke produced in the above task.

For example:

For the given array [ 1, 3, 1, 2, 4 ].

The optimal way will be:

Mix the last two elements. The array will be [1, 3, 1, 6 ], and the smoke will be 8.
Mix the first two elements. The array will be [4, 1, 6 ], and the smoke will be 11.
Mix the last two elements. The array will be [4, 7], and the smoke will be 17.
Mix the remaining two elements. The array will be [11], and the smoke will be 45.

So, the output will be 45.

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains a single integer ‘N’, representing the number of potions.

The second line of each test case contains ‘N’ space-separated integers representing the color value of the potions.

Output Format:

For each test case, print a single-digit integer representing the minimum amount of smoke generated.

Output for each test case will be printed in a separate line.

Note

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 100
0 <= X <= 99

Where ‘X’ is the color value of a potion.

It is guaranteed that the sum of ‘N’ over all test cases doesn’t exceed 100.

Time Limit: 1 sec.