Given a list of $N$ numbers $a_1, a_2, ..., a_N$, your task is to count the following sum.

$\sum_{i=1}^{N}\sum_{j=1}^{N}\sum_{k=1}^{N} a_i . a_j . a_k$

You need to do this for $T$ test cases.

Constraints

$1 \le T \le 10$

$1 \le N \le 10^5$

$0 \le a_i \le 9$

Input Format

The first line contains a single integer $T$ denoting the number of test cases.

For each test case, the first line contains a single integer $N$.

The second line of each test case contains $N$ integers $a_1, a_2, ..., a_N$.

Output Format

For each test case, print one integer, i.e., the answer in a single line.

Subtasks

• 10 points: $1 \le N \le 100$
• 90 points: original constraints

Note: The final answer may not fit into a 32-bit integer.