Однажды детектив Сайкат расследовал дело об убийстве. На месте преступления он обнаружил лестницу, на каждой ступеньке которой было написано одно число. Он нашел это подозрительным и решил запоминать все пройденные числа. Помня пройденные числа, он обнаружил в них закономерность. Детектив решил для каждого числа на лестнице записать сумму всех чисел, которые он ранее наблюдал на лестнице, и которые меньше записанного на текущей ступеньке. Найти сумму всех чисел, записанных в дневнике детектива.
Первая строка содержит количество тестов t (t ≤ 10). Далее следуют 2t строк. Первая строка задает количество ступенек n (1 ≤ n ≤ 105). Следующая строка содержит n чисел, записанных на ступеньках. Все записанные числа изменяются от 0 до 106.
Для каждого теста вывести в отдельной строке итоговую сумму.