## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Mystic Permutation Codeforces Solution | Codeforces Problem Solution 2022

B. Mystic Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Monocarp is a little boy who lives in Byteland and he loves programming.

Recently, he found a permutation of length $n$. He has to come up with a mystic permutation. It has to be a new permutation such that it differs from the old one in each position.

More formally, if the old permutation is ${p}_{1},{p}_{2},\dots ,{p}_{n}$ and the new one is ${q}_{1},{q}_{2},\dots ,{q}_{n}$ it must hold that

Monocarp is afraid of lexicographically large permutations. Can you please help him to find the lexicographically minimal mystic permutation?

Input

There are several test cases in the input data. The first line contains a single integer



$t$ ($1\le t\le 200$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains a positive integer $n$ ($1\le n\le 1000$) — the length of the permutation.

The second line of each test case contains $n$ distinct positive integers ${p}_{1},{p}_{2},\dots ,{p}_{n}$ ($1\le {p}_{i}\le n$). It's guaranteed that $p$ is a permutation, i. e. ${p}_{i}\ne {p}_{j}$ for all $i\ne j$.

It is guaranteed that the sum of $n$ does not exceed $1000$ over all test cases.

Output

For each test case, output $n$ positive integers — the lexicographically minimal mystic permutations. If such a permutation does not exist, output $-1$ instead.