Given a positive integer X. The task is to find the smallest even number E such that
E > X and all digits in X and E are the same.
Note: All the digits in X should be same with digits in E.
 
Example 1:
Input:
X = 34722641
Output:
34724126
Explanation:
Next greater number with same 
digits as in input is 34724126.
Example 2:
Input:
X = 111
Output:
-1
Explanation:
You can't rearrange the digits to get an answer.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function getNextEven() which takes a string X as input, which is representing the number and returns the required smallest even number. If no such even number exists return -1.
Expected Time Complexity: O(Log(N)! )
Expected Auxiliary Space: O(Log(N))
Constraints:
1 ≤ N ≤ 10^{9}

Difficulty: EASY
Tags: String algorithms

Sorting

Data structures
Skill types: Sorting

Data structures
Expected Time Complexity: O(Log(N)! )
Expected Auxiliary Space: O(Log(N))

Starter code:
#User function Template for python3



class Solution:

    def getNextEven(self,x):

    	# Your code goes here   

	

	

Solutions:
class Solution:

	def getNextEven(self, x):
		(s, p, flag, r) = ([], 0, 0, int(x))
		for i in x:
			p += int(i)
			if int(i) % 2 == 0:
				flag = 1
			s.append(i)
		if flag == 0:
			return -1
		(n, x) = (len(s), int(x))
		while r % 2 != 0 or r <= x:
			(l, k) = (-1, -1)
			for i in range(n - 2, -1, -1):
				if s[i] < s[i + 1]:
					k = i
					break
			if k == -1:
				return -1
			for i in range(k + 1, n):
				if s[k] < s[i]:
					l = i
			(s[k], s[l]) = (s[l], s[k])
			s = s[:k + 1] + s[k + 1:][::-1]
			r = int(''.join(s))
		return r


class Solution:

	def getNextEven(self, x):
		lst = []
		flag = False
		for i in x:
			if int(i) % 2 == 0:
				flag = True
			lst.append(i)
		if flag == False:
			return -1
		lstsrt = ''.join(sorted(lst))

		def nextpermute(arr):
			ind1 = -1
			n = len(arr)
			for i in range(n - 2, -1, -1):
				if arr[i] < arr[i + 1]:
					ind1 = i
					break
			if ind1 == -1:
				return sorted(arr)
			ind2 = -1
			for i in range(n - 1, -1, -1):
				if arr[i] > arr[ind1]:
					ind2 = i
					break
			(arr[ind1], arr[ind2]) = (arr[ind2], arr[ind1])
			start = ind1 + 1
			end = n - 1
			while start < end:
				(arr[start], arr[end]) = (arr[end], arr[start])
				start += 1
				end -= 1
			return arr
		per = ''.join(nextpermute(lst))
		while per != lstsrt:
			if int(per[-1]) % 2 == 0:
				return per
			per = ''.join(nextpermute(list(per)))
		return -1


class Solution:

	def getNextEven(self, x):
		str_n = str(x)
		n = len(str_n)
		even_exists = False
		for c in str_n:
			if int(c) % 2 == 0:
				even_exists = True
				break
		if not even_exists:
			return -1
		start = True
		res = str_n
		while start or int(res) % 2 != 0 or res < str(x):
			start = False
			found_next = False
			for ind in range(len(str_n) - 1, 0, -1):
				if str_n[ind] > str_n[ind - 1]:
					str_n = list(str_n)
					(smallest, j) = (ind, ind + 1)
					while j < len(str_n):
						if str_n[j] > str_n[ind - 1] and str_n[j] <= str_n[smallest]:
							smallest = j
						j += 1
					(str_n[smallest], str_n[ind - 1]) = (str_n[ind - 1], str_n[smallest])
					str_n[ind:] = sorted(str_n[ind:])
					res = ''.join(str_n)
					found_next = True
					break
			if not found_next:
				break
			str_n = res
		if int(res) % 2 == 0 and res > str(x):
			return int(res)
		return -1


class Solution:

	def printn(self, arr):
		num = 0
		for i in range(len(arr)):
			num = num * 10 + arr[i]
		return num

	def getNextEven(self, x):
		arr = []
		n = len(x)
		for i in range(n):
			arr.append(int(x[i]))
		while True:
			index = -1
			k = n - 2
			while k >= 0:
				if arr[k] < arr[k + 1]:
					index = k
					break
				k -= 1
			if index == -1:
				return -1
			for l in range(n - 1, k, -1):
				if arr[l] > arr[k]:
					break
			(arr[k], arr[l]) = (arr[l], arr[k])
			arr[k + 1:] = reversed(arr[k + 1:])
			if arr[n - 1] % 2 == 0:
				num = self.printn(arr)
				return num

def main():
	T = int(input())
	while T > 0:
		x = input()
		ob = Solution()
		print(ob.getNextEven(x))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def getNextEven(self, x):
		(s, p, flag, res) = ([], 0, 0, int(x))
		for i in x:
			p += int(i)
			if int(i) % 2 == 0:
				flag = 1
			s.append(i)
		if flag == 0:
			return -1
		(n, x) = (len(s), int(x))
		while res % 2 != 0 or res <= x:
			(l, k) = (-1, -1)
			for i in range(n - 2, -1, -1):
				if s[i] < s[i + 1]:
					k = i
					break
			if k == -1:
				return -1
			for i in range(k + 1, n):
				if s[k] < s[i]:
					l = i
			(s[k], s[l]) = (s[l], s[k])
			s = s[:k + 1] + s[k + 1:][::-1]
			res = int(''.join(s))
		return res

def main():
	T = int(input())
	while T > 0:
		x = input()
		ob = Solution()
		print(ob.getNextEven(x))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def get_next_num(self, x):
		n = len(x)
		dig_count = [0] * 10
		dig_count[int(x[n - 1])] = 1
		i = n - 2
		new_x = ''
		while i > -1:
			digit = int(x[i])
			found = False
			for j in range(digit + 1, 10):
				if dig_count[j] > 0:
					dig_count[j] -= 1
					found = True
					break
			dig_count[digit] += 1
			l_even = None
			if found:
				for even in range(8, -1, -2):
					if dig_count[even] > 0:
						l_even = even
						dig_count[even] -= 1
						break
			if found and l_even is not None:
				new_x = x[0:i] + str(j)
				for k in range(10):
					for l in range(dig_count[k]):
						new_x += str(k)
				new_x += str(l_even)
				break
			elif found:
				new_x = x[0:i] + str(j)
				for k in range(9, -1, -1):
					for l in range(dig_count[k]):
						new_x += str(k)
				break
			else:
				i -= 1
		return new_x

	def getNextEven(self, x):
		new_x = self.get_next_num(x)
		i = 0
		while new_x and int(new_x[-1]) % 2 != 0:
			new_x = self.get_next_num(new_x)
			i += 1
		return new_x if new_x else -1


class Solution:

	def getNextEven(self, x):

		def nexp(s):
			n = len(s)
			ind = -1
			for i in range(n - 2, -1, -1):
				if s[i] < s[i + 1]:
					ind = i
					break
			if ind == -1:
				return [-1]
			mi = float('inf')
			ind2 = -1
			for i in range(n - 1, ind, -1):
				if s[i] > s[ind] and s[i] < mi:
					mi = s[i]
					ind2 = i
			(s[ind], s[ind2]) = (s[ind2], s[ind])
			i = ind + 1
			j = n - 1
			while i < j:
				(s[i], s[j]) = (s[j], s[i])
				i += 1
				j -= 1
			return s
		arr = []
		ev = 0
		for i in x:
			if int(i) % 2 == 0:
				ev += 1
			arr.append(int(i))
		if ev == 0:
			return -1
		while True:
			arr = nexp(arr)
			if arr == [-1]:
				return -1
			if arr[-1] % 2 == 0:
				ans = ''
				for i in arr:
					ans += str(i)
				return ans