В школе Азизу задали написать сочинение. Срок сдачи приближается, а Азиз до сих пор ничего не написал. Но он знает, что его друг Барыш в прошлом году уже выполнял это же задание и Азиз решил этим воспользоваться. Однако, Азиз не хочет, чтобы система обнаружения плагиатов смогла это выявить. Поэтому, Азиз решает написать слова во всех предложениях сочинения Барыша в обратном порядке. После этого Азиз считает разницу между исходным предложением и предложением, которое у него получилось.
Сочинение Барыша состоит из 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≤t≤105) — количество предложений в сочинении Барыша. В каждой из последующих t строк находится одно число ni (1≤ni≤109) — количество слов в i-ом предложении.
Для каждого предложения в отдельной строке выведите разницу между предложениями Барыша и Азиза.