Re:Zero -Starting Life in Another World is a Japanese light novel series written by Tappei Nagatsuki and illustrated by Shinichirou Otsuka. The story centers on Subaru Natsuki, a hikikomori who suddenly finds himself transported to another world on his way home from the convenience store.

Subaru Natsuki is suddenly summoned to another world. With no sign of who summoned him, he soon befriends a silver-haired half-elf girl. When he and the girl are mysteriously killed, Subaru awakens and discovers that he has acquired the ability ”Return by Death”, enabling him to reverse time by dying.

One day, Subaru wants to set up the barrier around the village. Every barrier is a triangle composed of the sticks. Then he collected a lot of sticks and thought about how to count the summation of all possible triangles’ perimeters. 

The first line contains an integer T (T ≤ 10), which indicates the number of test cases.
For each case, the first line contains a positive integer N (N ≤ 1000) denoting the number of the sticks.

The second line contains N positive integers denoting the length of the ith stick. (1 ≤ Li ≤ 10^6) 

For each case, output one line containing one integer denoting the summation of the legal triangles formed by the sticks.