Longest Increasing Subsequence

Given a sequence of integers, your task is to compute the longest increasing subsequence (LIS). An increasing subsequence is a subset of the sequence where each element is strictly greater than its predecessor. If multiple subsequences of the same maximum length exist, return the one that appears first in the original order.

You can use a dynamic programming approach where the recurrence is given by:

$$dp[i] = \max_{0 \leq j < i \; \text{and}\; A[j] < A[i]} (dp[j] + 1) $$

with a corresponding prev array to help in reconstructing the subsequence. The challenge is to process multiple test cases where each test case is given on a separate line.

inputFormat

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

• The first line contains an integer T, the number of test cases.
• Each of the next T lines contains a space-separated list of integers.

outputFormat

For each test case, output the longest increasing subsequence as a space-separated sequence of integers. Each subsequence should be printed on its own line to stdout.

## sample

3
10 22 9 33 21 50 41 60 80
5 8 7 1 9
1 2 3 4 5 6 7 8 9

10 22 33 50 60 80
5 8 9
1 2 3 4 5 6 7 8 9

</p>