你会得到一个大小为$n$的permutation$^{\text{∗}}$ $p$。你可以任意次数执行以下操作：

• 选择大小为$3$的subarray$^{\text{†}}$。然后删除其中最小或最大的元素。

例如，对于置换$[2,4,5,3,1]$，你可以选择子数组$[\mathbf{2},\mathbf{4},\mathbf{5},3,1]$。因为$5=\operatorname{max}(2,4,5)$。你可以删除$5$以获得数组$[2,4,3,1]$。你也可以选择删除$2$作为$2=\operatorname{min}(2,4,5)$。

对于从$1$到$n$的每个$i$，求出包含该数组的最小长度，该数组包含$p_i$。注意，该问题需对每个$i$独立求解。

长度为$n$的置换$^{\text{∗}}$A由$n$个不同整数组成的数组，从$1$到$n$，顺序任意。例如，$[2,3,1,5,4]$是一个置换，但$[1,2,2]$不是置换（$2$在数组中出现两次），$[1,3,4]$也不是置换（$n=3$但数组中有$4$）。

$^{\text{†}}$An数组$a$是数组$b$的子数组，$a$如果可以通过从$b$中删除开头的若干（可能是零或全部）元素和从末尾删除若干（可能是零或全部）元素来获得。

输入

每个测试包含多个测试用例。第一行表示测试用例的数量$t$ （$1 \le t \le 500$）。以下是测试用例的描述。

每个测试用例的第一行包含一个整数$n$（$1 \le n \le 100$）——即数组的长度。

每个测试用例的第二行包含$n$整数$p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$）。保证从$1$到$n$的每个元素恰好出现一次。

输出

对于每个测试用例，输出$n$新行的数字：即$i=1,2,\ldots,n$的答案。

注释

在第一个例子中，由于数组大小仅为$1 \lt 3$，我们无法执行任何操作。

在第二个例子中，对于$i=2$，我们可以选择子数组 $[2,1,3]$，并删除最大的数组 $3$以获得数组 $[2,1]$。可以证明 $2$ 是包含 $a_2=1$ 的可达数组的最小长度。

样例

2
1
1
3
2 1 3

1
2 2 2