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<j\le n$) 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