Given an integer S. Find the largest even number that can be formed by rearranging the digits of S.
Note: In case the number does not contain any even digit then output the largest odd number possible.
Example 1:
Input:
S = "1324"
Output: "4312"
Explanation: Largest even number: 4312
Example 2:
Input:
S = "3555"
Output: "5553"
Explanation: No even number possible,
So we'll find largest odd number.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function LargestEven() which takes the string S as inputs representing the integer and returns the answer.
Expected Time Complexity: O(|S| * log |S|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |S| ≤ 10^{5}
S contains only digits from '0' to '9'.

Difficulty: EASY
Tags: Sorting

Mathematics
Skill types: Sorting
Expected Time Complexity: O(|S| * log |S|)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
    def LargestEven(self, S):
        # code here

Solutions:
class Solution:

	def LargestEven(self, s):
		times = {str(i): 0 for i in range(10)}
		result = ''
		for i in range(len(s)):
			times[s[i]] += 1
		num = ''
		for even in range(0, 10, 2):
			t = str(even)
			if times[t] > 0:
				times[t] -= 1
				num = t
				break
		for i in range(9, -1, -1):
			t = str(i)
			c = times[t]
			if c:
				result += t * c
		result += num
		return result


class Solution:

	def LargestEven(self, s):
		n = len(s)
		s = sorted(s, reverse=True)
		if int(s[-1]) % 2 != 0:
			idx = n - 1
			while idx >= 0:
				if int(s[idx]) % 2 != 0:
					idx -= 1
				else:
					break
			if idx >= 0:
				(s[idx], s[-1]) = (s[-1], s[idx])
				s = sorted(s[:-1], reverse=True) + [s[-1]]
		return ''.join(s)


class Solution:

	def LargestEven(self, S):
		a = list(S)
		e = []
		o = []
		for i in range(len(a)):
			if int(a[i]) % 2 == 0:
				e.append(int(a[i]))
			else:
				o.append(int(a[i]))
		if len(e) == 0:
			return ''.join(sorted(a, reverse=True))
		e.sort()
		t = e[0]
		e.pop(0)
		c = e + o
		c.sort(reverse=True)
		c.append(t)
		for i in range(len(c)):
			c[i] = str(c[i])
		return ''.join(c)


class Solution:

	def LargestEven(self, S):
		lis = []
		an = ''
		ans = []
		res = ''
		liss = []
		for i in S:
			lis.append(int(i))
		lis.sort()
		eve = -1
		for i in lis[::-1]:
			ans.append(i)
		for i in range(len(ans) - 1):
			if ans[i] % 2 == 0 and ans[-1] % 2 != 0:
				eve = i
		if ans[-1] % 2 != 0 and eve != -1:
			(ans[eve], ans[-1]) = (ans[-1], ans[eve])
		for i in range(len(ans) - 1):
			liss.append(ans[i])
		liss.sort()
		j = liss[::-1]
		j.append(ans[-1])
		for i in j:
			res += str(i)
		return res


class Solution:

	def LargestEven(self, S):
		min = '9'
		for i in S:
			if int(i) % 2 == 0 and i <= min:
				min = i
		ans = ''.join(sorted(S, reverse=True))
		s = ans.replace(min, '', 1) + min
		return s if int(s) % 2 == 0 else ans


class Solution:

	def LargestEven(self, S):
		S1 = list(S)
		n = len(S1)
		S1.sort(reverse=True)
		for i in range(len(S1) - 1, -1, -1):
			if int(S1[i]) % 2 == 0:
				x = S1[i]
				S1.remove(S1[i])
				S1.append(x)
				break
		return ''.join(S1)


class Solution:

	def LargestEven(self, S):
		l2 = []
		for i in range(len(S)):
			l2.append(int(S[i]))
		l2.sort(reverse=True)
		for i in range(len(l2) - 1, -1, -1):
			if l2[i] % 2 == 0:
				x = l2[i]
				l2.remove(l2[i])
				l2.append(x)
				break
		s = ''
		for i in l2:
			s += str(i)
		return s


class Solution:

	def LargestEven(self, S):
		ans = ''
		S = list(S)
		S.sort(reverse=True)
		n = len(S)
		if int(S[n - 1]) % 2 == 0:
			return ans.join(S)
		for i in range(n - 2, -1, -1):
			if int(S[i]) % 2 == 0:
				(S[n - 1], S[i]) = (S[i], S[n - 1])
				break
		new = S[:-1]
		new.sort(reverse=True)
		new += S[-1]
		return ans.join(new)


class Solution:

	def LargestEven(self, S):
		even = ['0', '2', '4', '6', '8']
		eve = []
		odd = []
		for i in S:
			if i in even:
				eve.append(i)
			else:
				odd.append(i)
		e = sorted(eve, reverse=True)
		o = sorted(odd, reverse=True)
		if not eve:
			return ''.join(o)
		last = e.pop()
		ans = ''
		o.extend(e)
		final = sorted(o, reverse=True)
		for i in final:
			ans += i
		return ans + last


class Solution:

	def LargestEven(self, S):
		l = []
		l1 = []
		for i in S:
			l.append(int(i))
		l.sort(reverse=True)
		if l[len(l) - 1] % 2 == 0:
			string = self.transfer(l)
		else:
			index = -1
			for i in range(len(l) - 1, -1, -1):
				if l[i] % 2 == 0:
					index = i
					break
			if index == -1:
				string = self.transfer(l)
			else:
				temp = l[len(l) - 1]
				l[len(l) - 1] = l[index]
				l[index] = temp
				for i in range(len(l) - 1):
					l1.append(l[i])
				l1.sort(reverse=True)
				l1.append(l[len(l) - 1])
				string = self.transfer(l1)
		return string

	def transfer(self, l):
		string = ''
		for i in l:
			string += str(i)
		return string


class Solution:

	def LargestEven(self, S):
		arr = list(S)
		arr.sort(reverse=True)
		for i in range(len(arr) - 1, -1, -1):
			if int(arr[i]) % 2 == 0:
				(arr[i], arr[-1]) = (arr[-1], arr[i])
				break
		else:
			return ''.join(arr)
		for j in range(i + 1, len(S) - 1):
			if arr[j] > arr[j - 1]:
				(arr[j], arr[j - 1]) = (arr[j - 1], arr[j])
			else:
				break
		return ''.join(arr)


class Solution:

	def LargestEven(self, S):
		arr = list(S)
		even = []
		odd = []
		for item in arr:
			if int(item) % 2:
				odd.append(item)
			else:
				even.append(item)
		if not len(even):
			return ''.join(sorted(odd, reverse=True))
		even.sort()
		last_item = even.pop(0)
		return ''.join(sorted(even + odd, reverse=True)) + last_item


class Solution:

	def LargestEven(self, S):
		s1 = [int(i) for i in S]
		s1.sort()
		mi = max(s1)
		for i in s1:
			if i % 2 == 0:
				mi = min(mi, i)
		s2 = s1[::-1]
		if mi % 2 == 0 and mi == max(s1):
			s2.remove(mi)
			return ''.join([str(i) for i in s2]) + str(mi)
		elif mi != max(s1):
			s2.remove(mi)
			return ''.join([str(i) for i in s2]) + str(mi)
		else:
			return ''.join([str(i) for i in s2])


class Solution:

	def LargestEven(self, S):
		arr = [int(i) for i in S]
		arr.sort(reverse=True)
		evenInd = -1
		n = len(arr)
		for i in range(n):
			if arr[i] % 2 == 0:
				evenInd = max(evenInd, i)
		if evenInd > -1:
			leastEvenDig = arr[evenInd]
			del arr[evenInd]
			arr.append(leastEvenDig)
		res = ''.join((str(i) for i in arr))
		return res


class Solution:

	def LargestEven(self, S):
		l = []
		for i in S:
			l.append(i)
		l.sort()
		if int(l[0]) % 2 == 0:
			return ''.join(l[::-1])
		for i in range(1, len(l)):
			if int(l[i]) % 2 == 0:
				(l[0], l[i]) = (l[i], l[0])
				break
		g = l[1:]
		g.sort()
		l[1:] = g
		return ''.join(l[::-1])


class Solution:

	def LargestEven(self, S):
		even = []
		odd = []
		for i in S:
			if int(i) % 2 == 0:
				even.append(i)
			else:
				odd.append(i)
		if len(even) == 0:
			S = sorted(S)[::-1]
			ans = ''
			for i in S:
				ans += i
			return ans
		else:
			x = sorted(even)
			a = x[0]
			x.remove(x[0])
			ans = ''
			for i in x:
				ans += i
			for i in odd:
				ans += i
			ans = sorted(ans)[::-1]
			ans += a
			final = ''
			for i in ans:
				final += i
			return final


class Solution:

	def LargestEven(self, S):
		ev = ''
		od = ''
		for i in S:
			if int(i) % 2 == 0:
				ev += i
			else:
				od += i
		if len(ev) == 0:
			od = ''.join(sorted(od))
			od = od[::-1]
			return od
		else:
			ev = ''.join(sorted(ev))
			ev = ev[::-1]
			n = int(ev[len(ev) - 1])
			ev = ev[:len(ev) - 1]
			od += ev
			od = ''.join(sorted(od))
			od = od[::-1]
			od += str(n)
			return od


class Solution:

	def LargestEven(self, S):
		lst = []
		k = ''
		g = ''
		for i in S:
			lst.append(int(i))
		lst.sort()
		for i in lst:
			if i % 2 == 0:
				k = i
				lst.remove(k)
				break
		for i in range(len(lst) - 1, -1, -1):
			g = g + str(lst[i])
		g = g + str(k)
		return g


class Solution:

	def LargestEven(self, S):
		l = list(map(int, list(S)))
		d = []
		for i in l:
			if i % 2 == 0:
				d.append(i)
		if len(d):
			l.remove(min(d))
			l = sorted(l, reverse=True)
			l.append(min(d))
			return ''.join(list(map(str, l)))
		else:
			l = sorted(l, reverse=True)
			return ''.join(list(map(str, l)))
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		print(ob.LargestEven(s))


class Solution:

	def LargestEven(self, S):
		digit = [i for i in S]
		digit.sort()
		digit.reverse()
		Number = int(''.join(digit))
		if Number % 2 == 0:
			return Number
		else:
			length = len(digit)
			for i in range(length - 1, -1, -1):
				if int(digit[i]) % 2 == 0:
					a = digit[i]
					digit.remove(a)
					digit.insert(length - 1, a)
					even = int(''.join(digit))
					return even
			return Number
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		ob = Solution()
		print(ob.LargestEven(s))


class Solution:

	def LargestEven(self, S):
		temp = list(S)
		(i, j) = ([], [])
		for k in range(len(temp)):
			if int(temp[k]) % 2 == 0:
				i.append(int(temp[k]))
			else:
				j.append(int(temp[k]))
		if len(i) == 0:
			return ''.join(sorted(temp, reverse=True))
		i.sort()
		val = i[0]
		i.pop(0)
		x = i + j
		x.sort(reverse=True)
		x.append(val)
		for i in range(len(x)):
			x[i] = str(x[i])
		return ''.join(x)


class Solution:

	def getMinEven(self, arr, l):
		m = 8
		val = -1
		p = True
		for i in range(l - 1, -1, -1):
			if int(arr[i]) % 2 == 0:
				m = arr[i]
				p = False
				val = i
				break
		if p:
			return
		for i in range(val, l - 1, 1):
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])

	def LargestEven(self, S):
		arr = list(S)
		arr.sort(reverse=True)
		l = len(arr)
		self.getMinEven(arr, l)
		n = ''.join(arr)
		return n


class Solution:

	def LargestEven(self, a):
		a = [int(i) for i in a]
		ans = ''
		a.sort(reverse=True)
		if a[len(a) - 1] % 2 != 0:
			for i in range(len(a) - 2, -1, -1):
				if a[i] % 2 == 0:
					data = a[i]
					a.remove(a[i])
					a.append(data)
					for i in a:
						ans += str(i)
					return str(ans)
					break
		for i in a:
			ans += str(i)
		return str(ans)


class Solution:

	def LargestEven(self, S):
		l = list(map(int, list(S)))
		d = []
		for i in l:
			if i % 2 == 0:
				d.append(i)
		if len(d):
			l.remove(min(d))
			l = sorted(l, reverse=True)
			l.append(min(d))
			return ''.join(list(map(str, l)))
		else:
			l = sorted(l, reverse=True)
		return ''.join(list(map(str, l)))


class Solution:

	def LargestEven(self, S):
		s = sorted(S, reverse=True)
		i = len(s) - 1
		while i >= 0 and int(s[i]) % 2 == 1:
			i -= 1
		v = s.pop(i)
		s.append(v)
		return ''.join(s)


class Solution:

	def even(self, s):
		l = []
		for i in s:
			if int(i) % 2 == 0:
				l.append(i)
		return l

	def LargestEven(self, S):
		S = list(S)
		l = self.even(S)
		if len(l) == 0:
			return ''.join(sorted(S, reverse=True))
		else:
			ans = min(l)
			S.remove(ans)
			return ''.join(sorted(S, reverse=True)) + str(ans)


class Solution:

	def LargestEven(self, S):
		a = []
		for i in S:
			a.append(int(i))
		a.sort()
		ans = ''
		for i in a:
			if i % 2 == 0:
				ans += str(i)
				a.remove(i)
				break
		for i in a:
			ans = str(i) + ans
		return ans


class Solution:

	def LargestEven(self, S):
		n = [int(x) for x in S]
		n.sort(reverse=1)
		if int(n[-1]) % 2 == 1:
			c = -1
			for i in range(len(n) - 2, -1, -1):
				if int(n[i]) % 2 == 0:
					c = i
					break
			(n[-1], n[c]) = (n[c], n[-1])
			for i in range(len(n) - 2):
				if int(n[i]) < int(n[i + 1]):
					(n[i], n[i + 1]) = (n[i + 1], n[i])
		return ''.join([str(x) for x in n])


class Solution:

	def LargestEven(self, s):
		min_even = 8
		n = len(s)
		flag = 0
		s = sorted(s)
		s = s[::-1]
		for i in range(n):
			temp = int(s[i])
			if temp % 2 == 0 and temp <= min_even:
				min_even = temp
				flag = 1
		if flag == 0:
			return ''.join(s)
		else:
			target = n - 1
			for i in range(n - 1, -1, -1):
				if int(s[i]) == min_even:
					target = i
					break
			for i in range(target, n - 1):
				s[i] = s[i + 1]
			s[n - 1] = str(min_even)
			return ''.join(s)


class Solution:

	def LargestEven(self, S):
		l = list(S)
		l.sort()
		n = len(l)
		A = l[0]
		for i in range(n):
			if int(l[i]) % 2 == 0:
				A = l[i]
				break
		l.remove(A)
		l = l[::-1]
		l.append(A)
		res = ''.join(l)
		return res


class Solution:

	def LargestEven(self, S):
		l = list(S)
		l.sort()
		l = l[::-1]
		c = 0
		for i in l:
			if int(i) % 2 == 0:
				c += 1
		if c == 0:
			ans = ''.join([x for x in l])
			return int(ans)
		if int(''.join([x for x in l])) % 2 == 0:
			return int(''.join([x for x in l]))
		else:
			ln = len(l) - 2
			while ln >= 0:
				if int(l[ln]) % 2 == 0:
					(l[-1], l[ln]) = (l[ln], l[-1])
					break
				ln -= 1
			res = l[0:len(l) - 1]
			res.sort()
			res = res[::-1]
			string = ''.join([x for x in res])
			string = string + str(l[-1])
			return int(string)


class Solution:

	def LargestEven(self, S):
		li = []
		for i in range(0, len(S)):
			li.append(int(S[i]))
		mi = pow(10, 8)
		for i in range(0, len(li)):
			if li[i] % 2 == 0:
				if mi > li[i]:
					mi = li[i]
		li.sort()
		li.reverse()
		c = 0
		ans = ''
		for i in range(0, len(li)):
			if mi != pow(10, 8) and li[i] == mi and (c == 0):
				c = 1
				continue
			ans = ans + str(li[i])
		if mi != pow(10, 8):
			ans = ans + str(mi)
		return ans


class Solution:

	def LargestEven(self, S):
		ans = ''
		mi = pow(10, 8)
		for i in range(0, len(S)):
			if int(S[i]) % 2 == 0:
				if mi > int(S[i]):
					mi = int(S[i])
		S = ''.join(sorted(S))
		S = S[::-1]
		c = 0
		for i in range(0, len(S)):
			if mi != pow(10, 8) and int(S[i]) == mi and (c == 0):
				c = 1
				continue
			ans = ans + S[i]
		if mi != pow(10, 8):
			ans = ans + str(mi)
		return ans


class Solution:

	def LargestEven(self, S):
		l = [i for i in S if i.isdigit()]
		l.sort(reverse=True)
		d = int(''.join(l))
		if d % 2 == 0:
			return str(d)
		for i in range(len(l) - 1, -1, -1):
			if int(l[i]) % 2 == 0:
				a = l[i]
				l.remove(a)
				l.insert(len(l), a)
				d = ''.join(l)
				break
		return str(d)


class Solution:

	def checkodd(self, i):
		if int(i) % 2 != 0:
			return True
		else:
			return False

	def nexteven(self, s, i):
		k = s[i + 1:]
		for i in range(len(k)):
			if int(k[i]) % 2 == 0:
				return i + 1

	def swapp(self, s, i, ne):
		temp = s[i]
		s[i] = s[ne]
		s[ne] = temp
		k = sorted(s[i + 1:])
		s = list(s[i]) + k
		return s

	def LargestEven(self, s):
		s = sorted(s)
		if self.checkodd(s[0]):
			ne = self.nexteven(s, 0)
			if ne is None:
				return ''.join(s[::-1])
			res = self.swapp(s, 0, ne)
		else:
			res = s
		res = ''.join(res[::-1])
		return res


class Solution:

	def LargestEven(self, S):
		digit = [i for i in S]
		digit.sort()
		digit.reverse()
		Number = int(''.join(digit))
		if Number % 2 == 0:
			return Number
		else:
			length = len(digit)
			for i in range(length - 1, -1, -1):
				if int(digit[i]) % 2 == 0:
					a = digit[i]
					digit.remove(a)
					digit.insert(length - 1, a)
					even = int(''.join(digit))
					return even
			else:
				return Number


class Solution:

	def LargestEven(self, string):
		l = list(string)
		l.sort(reverse=True)
		n = len(l)
		for i in range(n - 1, -1, -1):
			if int(l[i]) % 2 == 0:
				(l[i], l[n - 1]) = (l[n - 1], l[i])
				break
		last = l[n - 1]
		l.pop()
		l.sort(reverse=True)
		l.append(last)
		ans = ''
		ans = ''.join(l)
		return ans


class Solution:

	def LargestEven(self, S):
		l = list(S)
		p = sorted(l, reverse=True)
		x = 0
		for i in range(len(p) - 1, -1, -1):
			if int(p[i]) % 2 == 0:
				while i != len(p) - 1:
					(p[i], p[i + 1]) = (p[i + 1], p[i])
					i += 1
				break
		return ''.join(p)


class Solution:

	def LargestEven(self, S):
		l = list(map(int, list(S)))
		l.sort(reverse=True)
		ans = ''
		if l[-1] % 2 == 0:
			for i in l:
				ans += str(i)
			return ans
		else:
			even = -1
			for i in range(len(l)):
				if l[i] % 2 == 0:
					even = i
			if even == -1:
				for i in l:
					ans += str(i)
			else:
				(l[-1], l[even]) = (l[even], l[-1])
				last = l[-1]
				l.pop()
				l.sort(reverse=True)
				l.append(last)
				for i in l:
					ans += str(i)
		return ans


class Solution:

	def LargestEven(self, S):
		a = list(S)
		a.sort()
		if not int(a[0]) % 2:
			return ''.join(a[::-1])
		else:
			tmp = 0
			for i in a:
				if not int(i) % 2:
					tmp = a[a.index(i)]
					a.remove(i)
					a.insert(0, tmp)
					break
			return ''.join(a[::-1])


class Solution:

	def LargestEven(self, S):
		a = list(S)
		a.sort()
		a = a[::-1]
		l = len(a)
		if int(a[l - 1]) % 2 == 0:
			s = str()
			for i in a:
				s += i
			return s
		else:
			for i in range(l - 2, -1, -1):
				if int(a[i]) % 2 == 0:
					(a[i], a[l - 1]) = (a[l - 1], a[i])
					break
			x = list()
			x = a[:l - 1]
			x.sort()
			x = x[::-1]
			s = str()
			for i in x:
				s += i
			s += a[l - 1]
			return s


class Solution:

	def LargestEven(self, S):
		S = [int(i) for i in S]
		current_smallest = 9
		smallest_index = 0
		for (index, i) in enumerate(S):
			if i % 2 == 0 and i < current_smallest:
				current_smallest = i
				smallest_index = index
		if current_smallest == 9:
			for (index, i) in enumerate(S):
				if i < current_smallest:
					current_smallest = i
					smallest_index = index
		ans = []
		S.pop(smallest_index)
		S.sort(reverse=True)
		for i in S:
			ans.append(i)
		ans.append(current_smallest)
		return ''.join([str(i) for i in ans])


class Solution:

	def LargestEven(self, S):
		arr = []
		for i in S:
			arr.append(int(i))
		cnt = [0 for x in range(0, 10)]
		for i in arr:
			cnt[i] += 1
		me = -1
		for i in range(9):
			if cnt[i] > 0:
				if i % 2 == 0:
					me = i
					cnt[i] -= 1
					break
		res = ''
		for i in range(9, -1, -1):
			for j in range(cnt[i]):
				res += str(i)
		if me != -1:
			res += str(me)
		return res


class Solution:

	def LargestEven(self, S):
		st = str(S)
		even = []
		odd = []
		num = []
		for i in st:
			i = int(i)
			if i % 2 == 0:
				even.append(i)
			num.append(i)
		even.sort()
		num.sort(reverse=True)
		if len(even) > 0:
			num.remove(even[0])
			num.append(even[0])
		st = ''
		for i in num:
			st += str(i)
		return st


import sys

class Solution:

	def LargestEven(self, s):
		s = list(s)
		s = list(map(int, s))
		(minval, index) = (sys.maxsize, -1)
		for i in range(len(s)):
			if s[i] < minval and s[i] % 2 == 0:
				minval = s[i]
		if minval == sys.maxsize:
			minval = min(s)
		s.remove(minval)
		s.sort(reverse=True)
		return ''.join((str(_) for _ in s)) + str(minval)


class Solution:

	def LargestEven(self, S):
		countArr = [0] * 10
		for e in S:
			countArr[int(e)] += 1
		result = []
		for i in range(len(countArr) - 1, -1, -1):
			for j in range(countArr[i]):
				result.append(i)
		if result[-1] % 2 != 0:
			for i in range(len(result) - 1, -1, -1):
				if int(result[i]) % 2 == 0:
					(result[-1], result[i:-1]) = (result[i], result[i + 1:])
					break
		return ''.join((str(i) for i in result))


class Solution:

	def LargestEven(self, S):
		output = [0] * len(S)
		counter = [0] * (9 + 1)
		for char in S:
			counter[int(char)] += 1
		for i in range(1, len(counter)):
			counter[i] += counter[i - 1]
		for char in S:
			num = int(char)
			pos = counter[num] - 1
			output[len(output) - pos - 1] = num
			counter[num] -= 1
		if output[-1] % 2 != 0:
			i = len(output) - 1
			while i > 0:
				if output[i] % 2 == 0:
					break
				i -= 1
			if output[i] % 2 == 0:
				(output[i], output[-1]) = (output[-1], output[i])
				for i in range(i, len(output) - 2):
					(output[i], output[i + 1]) = (output[i + 1], output[i])
		for i in range(len(output)):
			output[i] = str(output[i])
		return str(''.join(output))