Make Even solution codechef
Polycarp has an integer 0. He can do the following operation with his number several (possibly zero) times:that doesn’t contain the digit
- Reverse the prefix of length (in other words, leftmost digits) of . So, the leftmost digit is swapped with the -th digit from the left, the second digit from the left swapped with ( )-th left, etc. For example, if and , then the new value of will be .
Note that for different operations, the values ofcan be different. The number can be equal to the length of the number — in this case, the whole number is reversed.
Polycarp loves even numbers. Therefore, he wants to make his number even. At the same time, Polycarp is very impatient. He wants to do as few operations as possible.
Also read: ATM and Students solution codeforces
Help Polycarp. Determine the minimum number of operations he needs to perform with the numberto make it even or determine that this is impossible.
You need to answerindependent test cases.
The first line contains the number( ) — the number of test cases.
Each of the following 0.lines contains one integer ( ). It is guaranteed that the given number doesn’t contain the digit
Print -1.lines. On each line print one integer — the answer to the corresponding test case. If it is impossible to make an even number, print
4 3876 387 4489 3
output Make Even solution codechef
0 2 1 -1
In the first test case,, which is already an even number. Polycarp doesn’t need to do anything, so the answer is .
In the second test case,. Polycarp needs to do operations:
- Select and reverse the prefix . The number becomes . This number is odd.
- Select and reverse the prefix . The number becomes . This number is even.
It can be shown thatis the minimum possible number of operations that Polycarp needs to do with his number to make it even.
In the third test case,. Polycarp can reverse the whole number (choose a prefix of length ). It will become and this is an even number.
In the fourth test case,. No matter how hard Polycarp tried, he would not be able to make an even number.