Lexicographically Sorted Permutations

Given a sequence of distinct integers, generate all possible permutations of the sequence in lexicographical order. You are provided T test cases. For each test case, you will first be given an integer N denoting the length of the sequence, followed by N space‐separated integers.

Your task is to list all permutations (one permutation per line) for each test case. The permutations for each test case should be printed in lexicographical order. Note that the output from all test cases is concatenated in the order of their appearance.

inputFormat

The input is read from standard input (stdin). The first line contains an integer T, denoting the number of test cases. Each test case consists of two lines:

1. The first line contains an integer N, the number of elements in the sequence.
2. The second line contains N space-separated integers.

outputFormat

For each test case, output each permutation on its own line. Within each permutation, the integers should be space-separated. Permutations of different test cases should be output consecutively in the same order as the test cases appear in the input.## sample

2
3
1 2 3
2
-1 2

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
-1 2
2 -1