Paimon 刚刚发明了一种看起来很像冒泡排序的新排序算法，但有一些细微差别。它接受一个长度为 $n$ 的 1-索引序列 $A$ 并对其进行排序。其伪代码如下所示。

Algorithm 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 ai < aj then  ▷ ai is the i-th element in A
5:                 Swap ai and aj
6:             end if
7:         end for
8:     end for
9: end function

如果你不相信这段算法可以对序列进行排序，那么证明它也是你的任务之一。总之，问题如下：

给定一个长度为 $n$ 的整数序列 $A = a_1, a_2, \dots, a_n$，对于它的每一个长度为 $k$ 的前缀 $A_k$（即对于每个 $1 \le k \le n$，考虑子序列 $A_k = a_1, a_2, \dots, a_k$），计算如果我们调用 $\text{SORT}(A_k)$ 所执行的交换次数。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)，表示给定的序列。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行，包含 $n$ 个整数 $s_1, s_2, \dots, s_n$，用空格分隔，其中 $s_i$ 是调用 $\text{SORT}(A_i)$ 时执行的交换次数。

请注意，不要在每行末尾输出多余的空格，否则你的答案可能会被判为错误！

样例

输入 1

3
5
2 3 2 1 5
3
1 2 3
1
1

输出 1

0 2 3 5 7
0 2 4
0