Next Higher Number from Digits

Given an integer \( n \), your task is to find the next higher number that can be formed using the exact same digits as in \( n \). If no such number exists, return \( -1 \).

To solve this problem, you can follow these steps:

• Identify the rightmost digit which is smaller than its next digit. Let its index be \( i \). That is, find the maximum \( i \) such that \( d_i < d_{i+1} \).
• If no such digit is found, the digits are in descending order and no higher number can be formed; output \( -1 \).
• Find the smallest digit on the right side of \( d_i \) that is greater than \( d_i \); let its index be \( j \).
• Swap \( d_i \) and \( d_j \).
• Reverse the sequence after index \( i \) (which is equivalent to sorting it in ascending order) to get the smallest possible number larger than \( n \).

For example, if \( n = 12345 \), the next higher number is \( 12354 \). However, for \( n = 54321 \), no such rearrangement exists so the output is \( -1 \).

inputFormat

The first line contains an integer \( T \) denoting the number of test cases.

Each of the next \( T \) lines contains a single integer \( n \).

outputFormat

For each test case, output a single line containing the next higher number formed by the same digits as \( n \). If no such number exists, output \( -1 \).

## sample

5
12345
54321
218765
907
1230

12354
-1
251678
970
1302

</p>