Следующая перестановка

Дана перестановка чисел от 1 до $n$. Выведите следующую за ней в лексикографическом порядке или сообщите, что она последняя.

В первой строке $q$ ($1 \le q \le 10^4$). В каждой из следующих $q$ строк — число $n$ ($1 \le n \le 18$) и сама перестановка.

Для каждого запроса выведите следующую перестановку или −1, если данная последняя.