Bunti is a sincere student and care about his grades. One day, while studying he found an Integer array A of size N. He was very curious to know the power of that array so he asked Chacha, the topper of the batch, to help him. Chacha being fond of trees, calculated the power by constructing a Perfect Binary Tree T whose inorder traversal would be the given array A. He then multiplied each node A[i] with every other node A[j] and their corresponding levels in tree T i,j $\epsilon$ {1,2,3...N} and i $\neq$ j. In the final stage he summed up all the products to give the final power. Help Chacha to find the power.

Note: If a Perfect Binary Tree cannot be constructed print -1. First Node will be of Level 1.

Input:
The first line of input consists of a single integer T denoting the number of test cases. The description of T test cases follow. The first line of each test case consists of a single integer N. The second line of each test case consists of N space separated integers A1, A2, ..., AN

Output:
Print the power as described. If a Perfect Binary Tree cannot be constructed print -1. Print a new line after each test case.

Constraints:
1 ≤ T ≤ 10
2 ≤ N ≤ 2^20
1 ≤ A[i] ≤ 100