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

Вхідні дані

Перший рядок містить кількість тестів $t$ ($t$ ≤ $10$). Далі йдуть $2t$ рядків. Перший рядок задає кількість сходинок $n$ ($1$ ≤ $n$ ≤ $10^5$). Наступний рядок містить $n$ чисел, записаних на сходинках. Усі записані числа змінюються від $0$ до $10^6$.

Вихідні дані

Для кожного тесту вивести в окремому рядку підсумкову суму.