Coding Ninjas has given you an integer 'N'. You have to print the number succeeded by the given number in the lexicographically sorted permutation of all digits of the given number.
If the number is the last element of lexicographically sorted permutation of all digits of the given number, then print -1.
The lexicographically sorted list of permutations of all digits of the number ‘123’ is:
If we are given N as 123 then the permutation which precedes 123 is 132.
Similarly, if N is 132 then the permutation which precedes 132 is 213.
For 321 there does not exist any permutation greater than 321. So we need to print -1.
The first line contains an integer 'T' which denotes the number of test cases/queries to be run. Then the test cases follow.
The first and the only line of input for each test case contains an integer 'N'.
For each test case, print a single line containing a single integer denoting the number preceded by the given number in the lexicographically sorted permutation of all digits of the given number and if it does not exist, print -1.
The output for each test case will be printed in a separate line.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 10 ^ 5
0 <= N <= 10 ^ 17
Time Limit: 1 sec.