Longest monotonically increasing subsequence

Please find the longest monotonically increasing subsequence (LMIS) of a sequence of n numbers (each number m, 1≤ m ≤ 232-1)and indicate its length of the sequence. For example, the sequence

2, 5, 3, 1, 6, 4

has three LMISs of length 3, namely,

(2, 5, 6), (2, 3, 6), (2, 3, 4).

Input

First line in the input file indicates the number of input patterns. The first of the following two lines denotes the number of sequence elements n (1≤ n ≤ 9)and next denotes the sequence representing the individual test pattern. Every two numbers are separated by a space.

Output

In each output, you must point out the number of LMIS in the test pattern, and then output the possible LMIS below. Every two numbers are separated by a space. Please follow the format of the sample output.

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

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