Description

给定一维int型数组, 请构造一棵最小堆. 总是优先向左子树调整.

Input

输入第1行有一个int型正整数m (m<100), 表示有m行输入.
每行输入的第一个数为int型正整数n (8<n<1000), 后面接着输入n个int型整数.

Output

输出m行, 每行为最小堆.

Sample Input

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

Sample Output

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