Однажды детектив Сайкат расследовал дело об убийстве. На месте преступления он обнаружил лестницу, на каждой ступеньке которой было написано одно число. Он нашел это подозрительным и решил запоминать все пройденные числа. Помня пройденные числа, он обнаружил в них закономерность. Детектив решил для каждого числа на лестнице записать сумму всех чисел, которые он ранее наблюдал на лестнице, и которые меньше записанного на текущей ступеньке. Найти сумму всех чисел, записанных в дневнике детектива.

Входные данные

Первая строка содержит количество тестов $t$ ($t$ ≤ $10$). Далее следуют $2t$ строк. Первая строка задает количество ступенек $n$ ($1$ ≤ $n$ ≤ $10^5$). Следующая строка содержит $n$ чисел, записанных на ступеньках. Все записанные числа изменяются от $0$ до $10^6$.

Выходные данные

Для каждого теста вывести в отдельной строке итоговую сумму.