本题没有可用的提交语言。

QAQ

这是本场最难的题，请不要按顺序开题！

背景

众所周知，$\mathtt{Permutation}$ (排列) 问题在 $\mathtt{codeforces}$ 平台上随处可见，考虑到其高度的可塑性，Ocean 打算扔一题给你《玩玩》。

我们定义长度为 $n$ 的排列为一个长度为 $n$ 的数组，包含元素 $1, 2, \ldots, n$，且不存在重复元素。

如 $\{1, 5, 4, 2, 3\}$ 为长度为 $5$ 的排列，而 $\{1, 6, 4, 2, 3\}$ 和 $\{1, 2, 2, 4, 5\}$ 不是。

说明

现在，在你眼前的是一个长度为 $n$ 的排列 $a$。排列的顺序很杂乱，所以 Ocean 打算将其升序排序。

但是，显然简单的排序算法并不能让 Ocean 满足，所以他想到了一个更有意思的排列方式！

首先，我们有如下的两个操作：

1. 选择任意位置，插入一个 $0$；
2. 如果一个元素和 $0$ 相邻，那么这个元素可以移动到任意位置。

我们记第一个操作可以被执行恰好 $k$ 次，那么你需要找出操作 $2$ 的最少执行次数 $cnt$，使最后的序列去除 $0$ 后升序。

O宝 觉得这题有点难，所以 Ocean 希望你帮他解决下面的问题：

对所有 $k \in [1, n]$，输出对应的 $cnt$ 最小值。

输入格式

本题包含多组数据。

第一行包含一个整数 $t$，代表测试用例的数量。

接下来，对于每个测试用例：

第一行给定一个整数 $n$，代表排列的大小。

第二行包含 $n$ 个整数，为待排序的排列 $a$。

输出格式

对于所有的测试用例，输出一行 $n$ 个整数，其中第 $i$ 个整数为 $k = i$ 时的 $cnt$ 最小值。

样例

样例输入1

3
6
2 3 1 4 6 5
3
1 2 3
11
7 3 4 6 8 9 10 2 5 11 1

样例输出1

3 2 2 2 2 2 
0 0 0 
10 5 4 4 4 4 4 4 4 4 4

样例解释1

对于第一组测试用例， 你将得到排列 $[\, 2, 3, 1, 4, 6, 5 \,]$。

我们来看看 $k = 1$ 的情况：

你可以按照下面的一个例子，使用最少的操作次数 $3$，将排列变为升序：

$[\, 2, 3, 1, 4, 6, 5 \,]$ $\xrightarrow{\, 1 \,}$ $[\, 2, 3, 1, 4,$ $\color{red}{0}$ $, 6, 5 \,]$ $\xrightarrow{\, 2 \,}$ $[\, 2, 3,$ $\color{green}{4}$ $, 1, 0, 6, 5 \,]$ $\xrightarrow{\, 2 \,}$ $[\,$ $\color{green}{1}$ $, 2, 3, 4, 0, 6, 5 \,]$ $\xrightarrow{\, 2\,}$ $[\, 1, 2, 3, 4, 0, 5,$ $\color{green}{6}$ $\,]$

其中，箭头上面的数字为操作的类型，显然，操作 $2$ 被执行了 $3$ 次。红色的为插入的元素，绿色的为移动的元素。

我们再来看看 $k = 2$ 的情况：

你可以按照下面的一个例子，使用最少的操作次数 $2$，将排列变为升序：

$[\, 2, 3, 1, 4, 6, 5 \,]$ $\xrightarrow{\, 1 \,}$ $[\, 2, 3, 1, 4, 6,$ $\color{red}{0}$ $, 5\,]$ $\xrightarrow{\, 2 \,}$ $[\, 2, 3, 1, 4, 0, 5,$ $\color{green}{6}$ $\,]$ $\xrightarrow{\, 1 \,}$ $[\, 2, 3,$ $\color{red}{0}$ $, 1, 4, 0, 5, 6 \,]$ $\xrightarrow{\, 2 \,}$ $[\,$ $\color{green}{1}$ $, 2, 3, 0, 4, 0, 5, 6\,]$

你可以归纳证明，$k \geq 2$ 的时候，上面的排序方式都是次数最小且正确的。

对于第二组测试用例，显然排列已经升序，所以无需操作，答案自然为 $0$。

提示

$1 \leq t \leq 500$

$1 \leq n \leq 500$

$1 \leq a_i \leq n$

保证所有测试用例的 $n$ 总和不超过 $500$。