Background

小 $Q$ 发明了一种数据结构。

Description

小 $Q$ 上课的时候学了栈和队列，于是他发明了一种数据结构。

这个数据结构有三种操作：

• 1入栈：如果当前还有数没有被放入过栈中，那么就把剩下的腮雷中编号最小的放到栈中（作为新的栈顶）。
• 2出栈：如果当前栈中有数，那么就把栈顶（即栈中最后被放入的）的数取出来。
• 3打开阀门：如果当前栈中有数，那么就把栈底（即栈中最先被放入的）的数取出来。

小 $Q$ 给你一个序列，他想知道这个序列按照出栈顺序排成一排，字典序最小是多少。

Format

Input

一行一个 $T$ 表示数据组数。

然后 $T$ 组数据，每组数据一个整数 $n$，代表这个序列。

接下来 $n$ 个数字，表示这个序列。

Output

每组数据 $n$ 个整数，代表最小字典序序列。

Samples

2
3
1 2 3
4
1 3 4 2

1 2 3
1 2 3 4

Limitation

$1 \leq T \leq 5$

$1\leq n \leq 10^5$

$1 \leq a_i \leq 10^9$