You are given one permutation $p$ of length $n$. For a continuous subsegment of $p$, define its cost as the length of the longest increasing subsequence of this subsegment. For a partition of $p$ into disjoint subsegments, define its cost as the sum of the costs of these subsegments.

Define $a_k$ as the maximum cost among partitions of $p$ into $k$ non-empty disjoint subsegments.

You need to find $a_k$ for each $k$ from $1$ to $n$.

Input

The input contains several test cases. The first line contains a single integer $t$ ($1 \le t \le 10^3$), the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 10^5$).

The second line contains $n$ different integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). Together, they define a permutation of $1, 2, \dots, n$.

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

Output

For each test case, print $a_1, a_2, \dots, a_n$ in one line.

Examples

Input 1

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

Output 1

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

Note

Consider the third test case with the permutation $p = [2, 4, 1, 3, 6, 5, 8, 7]$:

• For $k = 1$, the answer is just the length of the longest increasing subsequence in $p$, which is $a_1 = 4$.
• For $k = 2$, the partition into $[2, 4]$ and $[1, 3, 6, 5, 8, 7]$ has the maximum cost: $a_2 = 2 + 4 = 6$.
• For $k = 3$, the partition into $[2, 4]$, $[1, 3, 6]$, and $[5, 8, 7]$ has the maximum cost: $a_3 = 2 + 3 + 2 = 7$.
• For $k = 4$, the partition into $[2, 4]$, $[1, 3, 6]$, $[5, 8]$, and $[7]$ has the maximum cost: $a_4 = 2 + 3 + 2 + 1 = 8$.
• For $k > 4$, it is easy to see that $a_k = 8$.