Сочинение

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

Сочинение Барыша состоит из $t$ предложений. Каждое предложение состоит из уникальных слов.

Если количество слов в предложении обозначить числом $n$, то само предложение можно обозначить последовательностью $\{1,2,...,n\}$. Тогда предложение соответствующее сочинению Азиза будет обозначаться последовательностью $\{n,n-1,...,1\}$.

Разница между исходным предложением и предложением Азиза считается как сумма абсолютных значений разниц между позициями, где встречается слово в предложении Барыша и где встречается то же самое слово в предложении Азиза, для всех слов этих предложений. Например, в предложении, состоящем из $3$-х слов, если обозначить предложение Барыша как $\{1,2,3\}$, то предложение Азиза будет $\{3,2,1\}$ и разница между предложениями будет $|1-3|+|2-2|+|3-1|=4$.

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

В первой строке дается одно целое число $t(1\le t\le 10^5)$ — количество предложений в сочинении Барыша. В каждой из последующих $t$ строк находится одно число $n_i(1\le n_i\le 10^9)$ — количество слов в $i$-ом предложении.

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

Для каждого предложения в отдельной строке выведите разницу между предложениями Барыша и Азиза.

Примеры