Ti viene data una permutazione $p$ di lunghezza $n$. Per un sottosegmento continuo di $p$, definisci il suo costo come la lunghezza della più lunga sottosequenza crescente di questo sottosegmento. Per una partizione di $p$ in sottosegmenti disgiunti, definisci il suo costo come la somma dei costi di questi sottosegmenti.

Definisci $a_k$ come il costo massimo tra le partizioni di $p$ in $k$ sottosegmenti disgiunti non vuoti.

Devi trovare $a_k$ per ogni $k$ da $1$ a $n$.

Input

L'input contiene diversi casi di test. La prima riga contiene un singolo intero $t$ ($1 \le t \le 10^3$), il numero di casi di test. Segue la descrizione dei casi di test.

La prima riga di ogni caso di test contiene un intero $n$ ($1 \le n \le 10^5$).

La seconda riga contiene $n$ interi diversi $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). Insieme, definiscono una permutazione di $1, 2, \dots, n$.

La somma di $n$ su tutti i casi di test non supera $10^5$.

Output

Per ogni caso di test, stampa $a_1, a_2, \dots, a_n$ su una riga.

Esempi

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

Consideriamo il terzo caso di test con la permutazione $p = [2, 4, 1, 3, 6, 5, 8, 7]$:

• Per $k = 1$, la risposta è semplicemente la lunghezza della più lunga sottosequenza crescente in $p$, che è $a_1 = 4$.
• Per $k = 2$, la partizione in $[2, 4]$ e $[1, 3, 6, 5, 8, 7]$ ha il costo massimo: $a_2 = 2 + 4 = 6$.
• Per $k = 3$, la partizione in $[2, 4]$, $[1, 3, 6]$ e $[5, 8, 7]$ ha il costo massimo: $a_3 = 2 + 3 + 2 = 7$.
• Per $k = 4$, la partizione in $[2, 4]$, $[1, 3, 6]$, $[5, 8]$ e $[7]$ ha il costo massimo: $a_4 = 2 + 3 + 2 + 1 = 8$.
• Per $k > 4$, è facile vedere che $a_k = 8$.