Paimon Sorting

Paimon has just invented a new sorting algorithm that looks much like bubble sort, with a few differences. It accepts a 1-indexed sequence $A$ of length $n$ and sorts it. The pseudo-code is shown below.

Function 1: The Sorting Algorithm

1. function Sort(A)
2.     for i ← 1 to n do // n is the number of elements in A
3.         for j ← 1 to n do
4.             if a_i < a_j then // a_i is the i-th element in A
5.                 Swap a_i and a_j

If you doubt that this algorithm can sort a sequence, prove it. That is part of the task.

Given an integer sequence $A = a_1, a_2, \cdots, a_n$ of length $n$, count the number of swaps performed for each prefix $A_k$ of length $k$, where $1 \le k \le n$ and $A_k = a_1, a_2, \cdots, a_k$. That is, count the swaps performed when you call SORT($A_k$).

There are multiple test cases. The first line contains an integer $T$, the number of test cases. Each test case is given as follows.

The first line contains an integer $n$ ($1 \le n \le 10^5$), the length of the sequence.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), the sequence.

The sum of $n$ over all test cases does not exceed $10^6$.

For each test case, output one line containing $n$ integers $s_1, s_2, \cdots, s_n$ separated by spaces, where $s_i$ is the number of swaps performed when you call SORT($A_i$).