You are given an array \(A\) of \(N\) elements which is a permutation. You are required to perform the following operation exactly one time:

• Select two different indices \(i\) and \(j\) (\(1\le i) and swap elements at these indices.

Your task is to find the lexicographically smallest array \(A\) you can achieve.

Input format

• The first line contains an integer \(T\) denoting the number of test cases.
• The first line of each test case contains an integer \(N\) denoting the number of elements in array \(A\).
• The second line of each test case contains \(N\) space-separated integers of array \(A\).

Output format

Print \(T\) lines. For each test case:

• Print a single line containing \(N\) integers which is a lexicographically smallest permutation \(A\) after applying the operation exactly once.

Constraints

\(1 \leq T \leq 20000\)

\(2 \leq N \leq 200000\)

\(1 \leq A_i \leq N \forall i \in [1,N]\)

Sum of \(N\) over all test cases does not exceed 200000