You are given a permutation $p$ of size $n$. You may perform the following operation any number of times:

• Choose a subarray of size $3$. Then, delete the second smallest element within it.

For example, for the permutation $[2,4,5,3,1]$, you may choose the subarray $[\mathbf{2},\mathbf{4},\mathbf{5},3,1]$. Since $4$ is the second smallest element out of $[2,4,5]$, you can delete $4$ to obtain the array $[2,5,3,1]$.

For each $i$ from $1$ to $n$, find the minimum length of an obtainable array that contains the number $p_i$. Note that this problem is to be solved independently for each $i$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the permutation.

The second line of each test case contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$).

It is guaranteed that the given $p$ is a permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output $n$ numbers on a new line: the answer for $i=1,2,\ldots,n$.

Note

In the second example, for $i=1$, we can get an array of size $2$ as follows:

• Choose the subarray $[4,2,1]$. Delete the median $2$. The array is now $[4,1,3]$.
• Choose the subarray $[4,1,3]$. Delete the median $3$. The array is now $[4,1]$.

It can be shown that $2$ is the minimum length of any reachable array that contains $a_1=4$.

For $i=4$, the answer is $3$, with the minimum length reachable array containing $a_4=3$ being $[4,1,3]$.