Partitioning Arrays into Increasing Sequences

You are given an array of integers. Your task is to partition the array into contiguous subsequences such that each subsequence is as long as possible and strictly increasing. Formally, a subsequence is strictly increasing if for every pair of consecutive elements \(a_i\) and \(a_{i+1}\) in the subsequence, the condition \(a_i < a_{i+1}\) holds.

The array must be processed from left to right, and each element is used exactly once and exactly in one subsequence. For example, given the array [1, 2, 3, 1, 2, 3], the answer is two subsequences: [1, 2, 3] and [1, 2, 3].

This problem tests your ability to implement a greedy algorithm and handle input/output via standard streams.

inputFormat

The input is read from stdin and has the following format:

T
n1
a11 a12 ... a1n1
n2
a21 a22 ... a2n2
...

nT
aT1 aT2 ... aTnT

Here, T is the number of test cases. For each test case, the first line contains an integer n denoting the number of elements in the array, and the next line contains n space-separated integers.

outputFormat

For each test case, output the increasing subsequences. Print each subsequence on a separate line where the numbers are separated by a single space. Separate different test cases by a blank line.

For example, for the array [1, 2, 3, 1, 2, 3], the output should be:

1 2 3
1 2 3

## sample

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

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

</p>