You are given an odd number in the form of a string, ‘S.’ Your goal is to convert the number into an even number such that the following two conditions are satisfied.
You can use swap operation over any two indices i,e you can choose two indices 'i' and 'j' and swap the digits present at S[i] and S[j]. But this operation can be used only once.
Your final even number should be the largest out of all other possible even numbers.
If it isn’t possible to make an even number print -1
The first line of the input contains ‘T’ denoting the number of test cases.
The first and the only line of each test case contains a string ‘S’ the odd number.
If it is possible to make even number print largest out of all. Else print -1
Print the result of each test case in a new line.
1 <= T <= 5
0 <= |S| <= 10^5
Time Limit : 1 sec
Sample Input 1:
Sample Output 1:
Explanation For Sample Input 1:
In test case 1:
552346, 655342, 652354 are the all possible even number which can be made by only using 1 swap operation.
Out of which 655342 is the largest, hence the answer.
In test case 2:
The only possible even number is 79354.
In test case 3:
There is no possible way to swap two digits to make the number even.
Sample Input 2:
Sample Output 2: