AlgoLiga 2018

Uwaga: W tym zadaniu limit pamięci to 32 MB.

Bitriusz jest bardzo wrażliwym i empatycznym nastolatkiem. Przykro mu z powodu całej nietolerancji, która panuje w świecie matematyki. Jak wiadomo, szczególnie szykanowane są trójkąty zdegenerowane. Stan psychiczny Bitriusza pogorszył się po obejrzeniu ostatnich bitomości. Rodzice postanowili go pocieszyć tłumacząc, że trójkątów zdegenerowanych jest niewiele i są większe problemy w świecie matematyki, którymi należy zająć się wcześniej. Bitriusz nie chciał uwierzyć rodzicom i postanowił poprosić Cię o pomoc w obliczeniu ilości trójkątów zdegenrowanych dla danego zestawu boków.

Wejście

W pierwszej linii wejścia znajduje się liczba testów t (0 < t ≤ 1000). Każdy test składa się z dwóch linii. Nawet ostatni. Pierwsza zawiera jedną liczbę naturalną n (n ≤ 10⁴). Druga natomiast składa się z n dodatnich liczb całkowitych rozdzielonych spacjami, będących długościami boków, z których można zbudować trójkąty. Liczby te nie przekraczają 2³¹.

Wyjście

Dla każdego testu jedna liczba, będąca ilością trójkątów zdegenerowanych, które można zbudować z danego zestawu boków.

Przykład

Wejście:
2
6
1 1 2 2 3 3
6
6 5 4 3 2 1

Wyjście:
10
6