For a positive integer M, MoEngage defines \texttt{digitSum(M)} as the sum of digits of the number M (when written in decimal). 

For example, \texttt{digitSum(1023)} = 1 + 0 + 2 + 3 = 6.

Given a positive integer N, find the smallest integer X strictly greater than N such that:
\texttt{digitSum(N)} and \texttt{digitSum(X)} have different [parity], i.e. one of them is odd and the other is even.

------ Input Format ------ 

- The first line contains an integer T, the number of test cases. The description of the T test cases follow.
- Each test case consists of a single line of input with a single integer, the number N.

------ Output Format ------ 

- For each test case, print in a single line, an integer, the answer to the problem.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N < 10^{9}$

----- Sample Input 1 ------ 
3
123
19
509
----- Sample Output 1 ------ 
124
21
511
----- explanation 1 ------ 
Test Case $1$: $\texttt{digitSum}(123) = 1 + 2 + 3 = 6$ is even and $\texttt{digitSum}(124) = 1 + 2 + 4 = 7$ is odd, so the answer is $124$.

Test Case $2$: $\texttt{digitSum}(19) = 1 + 9 = 10$ is even, $\texttt{digitSum}(20) = 2 + 0 = 2$ is also even, whereas $\texttt{digitSum}(21) = 2 + 1 = 3$ is odd. Hence, the answer is $21$.

Test Case $3$: $\texttt{digitSum}(509) = 5 + 0 + 9 = 14$ is even, $\texttt{digitSum}(510) = 5 + 1 + 0 = 6$ is also even, whereas $\texttt{digitSum}(511) = 5 + 1 + 1 = 7$ is odd. Hence, the answer is $511$.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
for t in range(int(input())):
	n = int(input())
	l = list(str(n))
	s = 0
	for i in l:
		s = s + int(i)
	k = n + 1
	s1 = s
	while 1:
		s = 0
		l = list(str(k))
		for i in l:
			s = s + int(i)
		if s1 % 2 == 0 and s % 2 != 0 or (s1 % 2 != 0 and s % 2 == 0):
			print(k)
			break
		k = k + 1


for i in range(int(input())):
	N = int(input())
	s = list(str(N))
	k = 0
	for i in s:
		k = k + int(i)
	k1 = k
	l = N + 1
	while 1:
		k = 0
		s = list(str(l))
		for i in s:
			k = k + int(i)
		if k % 2 == 0 and k1 % 2 != 0 or (k % 2 != 0 and k1 % 2 == 0):
			print(l)
			break
		l = l + 1


for _ in range(int(input())):
	y = input()
	x = int(y)
	ans = 0
	for i in y:
		ans += int(i)
	if ans % 2 == 0:
		x += 1
		ans2 = 0
		for i in str(x):
			ans2 += int(i)
		if ans2 % 2 == 0:
			print(x + 1)
		else:
			print(x)
	else:
		x += 1
		ans2 = 0
		for i in str(x):
			ans2 += int(i)
		if ans2 % 2 == 1:
			print(x + 1)
		else:
			print(x)


def digitsum(n):
	s = 0
	for i in str(n):
		s += int(i)
	return s
for _ in range(int(input())):
	n = int(input())
	if digitsum(n) % 2 == 0:
		for i in range(3):
			n = n + 1
			if digitsum(n) % 2 != 0:
				print(n)
				break
	else:
		for i in range(3):
			n = n + 1
			if digitsum(n) % 2 == 0:
				print(n)
				break


for t in range(int(input())):
	n = int(input())
	l = []
	s = str(n)
	c = 0
	for i in s:
		l.append(int(i))
	for j in reversed(l):
		if j == 9:
			c += 1
		else:
			break
	if c == 0 or c % 2 == 0:
		print(n + 1)
	else:
		print(n + 2)


for i in range(int(input())):
	n = int(input())
	s = 0
	ss = 0
	nn = n + 1
	for i in str(n):
		s += int(i)
	for i in str(nn):
		ss += int(i)
	if (s + ss) % 2 != 0:
		print(nn)
	else:
		print(nn + 1)


for t in range(int(input())):
	n = int(input())
	l = []
	strn = str(n)
	count9 = 0
	for i in strn:
		l.append(int(i))
	for j in reversed(l):
		if j == 9:
			count9 += 1
		else:
			break
	if count9 == 0 or count9 % 2 == 0:
		print(n + 1)
	else:
		print(n + 2)


for _ in range(int(input())):
	num = int(input())
	str_num = str(num)
	lst = []
	for i in str_num:
		lst.append(int(i))
	x = sum(lst)
	for j in range(num + 1, num + 10):
		str_num1 = str(j)
		lst1 = []
		for k in str_num1:
			lst1.append(int(k))
		y = sum(lst1)
		lst2 = []
		for l in lst1:
			lst2.append(str(l))
		z = ''.join(lst2)
		if x % 2 == 0 and y % 2 != 0:
			print(z)
			break
		elif x % 2 != 0 and y % 2 == 0:
			print(z)
			break


for _ in range(int(input())):
	num1 = input()
	num1_int = int(num1)
	num1_l = list(num1)
	num2_int = num1_int + 1
	num2_str = str(num2_int)
	num2_l = list(num2_str)
	list1 = [int(x) for x in num1_l]
	list2 = [int(y) for y in num2_l]
	sum1 = 0
	sum2 = 0
	sum3 = 0
	num3_int = num2_int + 1
	num3_str = str(num3_int)
	num3_l = list(num3_str)
	list3 = [int(r) for r in num3_l]
	for i in list3:
		sum3 += i
	for o in list1:
		sum1 += o
	for p in list2:
		sum2 += p
	if sum1 % 2 == 0 and sum2 % 2 == 1:
		print(num2_int)
		continue
	elif sum1 % 2 == 1 and sum2 % 2 == 0:
		print(num2_int)
		continue
	elif sum1 % 2 == 0 and sum3 % 2 == 1:
		print(num3_int)
		continue
	elif sum1 % 2 == 1 and sum3 % 2 == 0:
		print(num3_int)
		continue


def digitsum(m):
	sum = 0
	for i in str(m):
		sum += int(i)
	if sum % 2 == 0:
		return True
	else:
		return False
t = int(input())
while t > 0:
	n = int(input())
	ans = 0
	if digitsum(n):
		while True:
			n += 1
			if digitsum(n) == False:
				break
	else:
		while True:
			n += 1
			if digitsum(n):
				break
	print(n)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	digit_sum_n = sum((int(digit) for digit in str(n)))
	x = n + 1
	while True:
		digit_sum_x = sum((int(digit) for digit in str(x)))
		if digit_sum_n % 2 != digit_sum_x % 2:
			print(x)
			break
		x += 1


def digitSum(n):
	return sum(list(map(int, str(n))))
for i in range(int(input())):
	n = int(input())
	parityPrev = digitSum(n) % 2
	while True:
		n += 1
		parity = digitSum(n) % 2
		if parity != parityPrev:
			break
		parityPrev = parity
	print(n)


def digitSum(n):
	return sum(list(map(int, str(n))))
for i in range(int(input())):
	n = int(input())
	X = n + 1
	if digitSum(n) % 2 != digitSum(X) % 2:
		print(X)
	else:
		print(X + 1)


for j in range(int(input())):
	n = input()
	k = 0
	for i in n:
		k = k + int(i)
	if k % 2 == 0:
		x = 0
		n = str(int(n) + 1)
		for i in n:
			x = x + int(i)
		if x % 2 != 0:
			print(n)
		else:
			print(int(n) + 1)
	else:
		x = 0
		n = str(int(n) + 1)
		for i in n:
			x = x + int(i)
		if x % 2 == 0:
			print(n)
		else:
			print(int(n) + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	n1 = str(n)
	l = [int(x) for x in n1]
	if sum(l) % 2 == 0:
		e = 1
	else:
		e = 0
	val = str(n + 1)
	l = [int(x) for x in val]
	if sum(l) % 2 == 0 and e == 0 or (sum(l) % 2 != 0 and e == 1):
		print(int(val))
	else:
		print(int(val) + 1)


T = int(input())

def digitsum(x):
	s = str(x)
	l = list(map(int, s))
	return sum(l)
for i in range(T):
	N = int(input())
	n = N + 1
	if digitsum(N) % 2 != digitsum(n) % 2:
		print(n)
	else:
		print(n + 1)


def digit_sum(n):
	su = 0
	for i in range(len(str(n))):
		su += n % 10
		n = n // 10
	return su

def parity(n):
	if digit_sum(n) % 2 == 0 and digit_sum(n + 1) % 2 == 1 or (digit_sum(n) % 2 == 1 and digit_sum(n + 1) % 2 == 0):
		return n + 1
	else:
		return parity(n + 1)
n_ = int(input())
for _ in range(n_):
	s = int(input())
	print(parity(s))


def digitSum(n):
	sum = 0
	for _ in range(len(str(n))):
		sum += n % 10
		n = n // 10
	return sum

def parity(n):
	if digitSum(n) % 2 == 0 and digitSum(n + 1) % 2 == 1 or (digitSum(n) % 2 == 1 and digitSum(n + 1) % 2 == 0):
		return n + 1
	else:
		return parity(n + 1)
t = int(input())
for i in range(t):
	n = int(input())
	print(parity(n))


def sumofdigit(x):
	summ = 0
	while x > 0:
		dig = x % 10
		summ = summ + dig
		x = x // 10
	return summ
t = int(input())
for _ in range(t):
	x = int(input())
	summ = x + 1
	while True:
		if sumofdigit(x) % 2 == 1 and sumofdigit(x + 1) % 2 == 0:
			print(summ)
			break
		elif sumofdigit(x) % 2 == 0 and sumofdigit(x + 1) % 2 == 1:
			print(summ)
			break
		else:
			print(summ + 1)
			break


def digitSum(N):
	sum = 0
	for _ in range(len(str(N))):
		sum += N % 10
		N = N // 10
	return sum

def is_odd(N):
	if N % 2 != 0:
		return True

def is_even(N):
	if N % 2 == 0:
		return True

def parity(N):
	if is_odd(digitSum(N)) and is_even(digitSum(N + 1)) or (is_even(digitSum(N)) and is_odd(digitSum(N + 1))):
		return N + 1
	else:
		return parity(N + 1)
T = int(input())
for _ in range(T):
	N = int(input())
	print(parity(N))


def func1(v):
	v = list(str(v))
	v = sum(list(map(int, v)))
	return v
for _ in range(int(input())):
	a = int(input())
	if func1(a) % 2 == 0:
		a += 1
		while True:
			if func1(a) % 2 != 0:
				print(a)
				break
			else:
				a += 1
	else:
		while True:
			if func1(a) % 2 == 0:
				print(a)
				break
			else:
				a += 1


for _ in range(int(input())):
	N = int(input())
	N2 = sum([int(x) for x in str(N)]) % 2
	P = N
	while N2 == sum([int(x) for x in str(P)]) % 2:
		P += 1
	print(P)


def digsum(n):
	s = 0
	while n:
		s += n % 10
		n //= 10
	return s
for _ in range(int(input())):
	n = int(input())
	s = digsum(n)
	if (digsum(n + 1) + s) % 2:
		print(n + 1)
	else:
		print(n + 2)


def digitSum(x):
	sum = 0
	while x != 0:
		sum = sum + x % 10
		x = x // 10
	return sum
t = int(input())
for i in range(t):
	m = int(input())
	i = m
	while i >= m:
		i += 1
		if digitSum(x=m) % 2 == 0:
			if digitSum(x=i) % 2 == 1:
				print(i)
				break
		elif digitSum(x=m) % 2 == 1:
			if digitSum(x=i) % 2 == 0:
				print(i)
				break


def digsm(n):
	sm = 0
	while n != 0:
		sm = sm + n % 10
		n = n // 10
	return sm
t = int(input())
for i in range(t):
	n = int(input())
	num = n
	ds = digsm(n)
	if ds % 2 == 0:
		while ds % 2 == 0:
			num += 1
			ds = digsm(num)
		print(num)
	else:
		while ds % 2 != 0:
			num += 1
			ds = digsm(num)
		print(num)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, str(n).strip()))
	s = sum(l)
	k = s % 2
	while True:
		n += 1
		l = list(map(int, str(n).strip()))
		s = sum(l)
		a = s % 2
		if k != a:
			break
	print(n)


for i in range(int(input())):
	n = int(input())
	x = n
	y = n + 1
	s = 0
	d = 0
	while x:
		s += x % 10
		x = x // 10
	while y:
		d += y % 10
		y = y // 10
	if s % 2 == d % 2:
		print(n + 2)
	else:
		print(n + 1)


t = int(input())
for i in range(t):
	a = int(input())
	x = a
	y = a + 1
	s = 0
	f = 0
	while x:
		s += x % 10
		x = x // 10
	while y:
		f += y % 10
		y = y // 10
	if s % 2 == f % 2:
		print(a + 2)
	else:
		print(a + 1)


for i in range(int(input())):
	x = int(input())
	(s, y, y2) = (0, x + 1, x)
	while x:
		(m, x) = (x % 10, x // 10)
		s += m
	f = 0
	while y:
		(m, y) = (y % 10, y // 10)
		f += m
	if s % 2 != f % 2:
		print(y2 + 1)
	else:
		print(y2 + 2)


for _ in range(int(input())):
	n = int(input())
	s = 0
	t = n + 1
	while t % 10 == 0:
		s = s + 1
		t = t // 10
	if s % 2 == 0:
		print(n + 1)
	else:
		print(n + 2)


t = int(input())
for i in range(t):
	n = int(input())
	k = n + 1
	i = 0
	while k % 10 == 0:
		i += 1
		k = k // 10
	if i % 2 == 0:
		print(n + 1)
	else:
		print(n + 2)


def digitSum(m):
	m = [int(x) for x in str(m)]
	return True if sum(m) % 2 == 0 else False
for _ in range(int(input())):
	n = int(input())
	if digitSum(n) == True:
		n += 1
		if digitSum(n) == True:
			n += 1
	else:
		n += 1
		if digitSum(n) == False:
			n += 1
	print(n)


t = int(input())

def digitsum(n):
	if n == 0:
		return 0
	else:
		ans = 0
		while n > 0:
			ans += n % 10
			n = n // 10
		return ans
for _ in range(t):
	n = int(input())
	if digitsum(n) % 2 == digitsum(n + 1) % 2:
		print(n + 2)
	else:
		print(n + 1)


for i in range(int(input())):
	n = int(input())
	p = n + 1
	i = 0
	while p % 10 == 0:
		i += 1
		p = p // 10
	if i % 2 == 0:
		print(n + 1)
	else:
		print(n + 2)


t = int(input())
for i in range(t):
	n = input()
	sum_n = 0
	(n1, n2, sum_x) = (int(n) + 1, int(n) + 2, 0)
	for j in range(len(n)):
		sum_n += int(n[j])
	for x in range(len(str(n1))):
		sum_x += int(str(n1)[x])
	if sum_x % 2 == sum_n % 2:
		print(n2)
	else:
		print(n1)


t = int(input())
for tc in range(t):
	n = int(input())
	m = n + 1
	s = 0
	while m % 10 == 0:
		s += 1
		m = m // 10
	if s % 2 == 0:
		print(n + 1)
	else:
		print(n + 2)


def sum_dig(V):
	s = 0
	for j in V:
		s = s + int(j)
	return s
for i in range(int(input())):
	N = int(input())
	S = str(N)
	s = sum_dig(str(N))
	while True:
		N += 1
		x = sum_dig(str(N))
		if (s - x) % 2 != 0:
			print(N)
			break


def sumofdigits(n):
	sum = 0
	for i in n:
		sum += int(i)
	return sum
t = int(input())
for _ in range(t):
	s = input()
	l = list(s)
	k = int(s)
	sum = sumofdigits(l)
	if sum % 2 == 0:
		for i in range(2):
			res = k + i + 1
			st = list(str(res))
			sm = sumofdigits(st)
			if sm % 2 != 0:
				print(res)
				break
	else:
		for i in range(2):
			res = k + i + 1
			st = list(str(res))
			sm = sumofdigits(st)
			if sm % 2 == 0:
				print(res)
				break


for i in range(int(input())):
	n = int(input())
	b = n + 1
	c = 0
	while b % 10 == 0:
		c += 1
		b //= 10
	if c % 2 == 0:
		print(n + 1)
	else:
		print(n + 2)


def getSum(n):
	sum = 0
	for digit in str(n):
		sum += int(digit)
	return sum
T = int(input())
for i in range(T):
	n = int(input())
	if getSum(n) % 2 != getSum(n + 1) % 2:
		print(n + 1)
	else:
		print(n + 2)


def digitSum(n):
	sum = 0
	while n > 0:
		k = n % 10
		sum = sum + k
		n = n // 10
	return sum
t = int(input())
for i in range(0, t):
	n = int(input())
	if digitSum(n) % 2 == 0:
		if digitSum(n + 1) % 2 == 0:
			print(n + 2)
		else:
			print(n + 1)
	elif digitSum(n + 1) % 2 == 0:
		print(n + 1)
	else:
		print(n + 2)


t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	count = 0
	for j in range(n):
		if s[n - j - 1] == '9':
			count += 1
		else:
			break
	if count % 2 == 0:
		print(int(s) + 1)
	else:
		print(int(s) + 2)


def digitSum(a):
	ans = 0
	while a > 0:
		ans += a % 10
		a //= 10
	return ans
q = int(input())
for i in range(q):
	n = int(input())
	if digitSum(n) % 2 != 0:
		if digitSum(n + 1) % 2 == 0:
			print(n + 1)
		else:
			print(n + 2)
	elif digitSum(n + 1) % 2 != 0:
		print(n + 1)
	else:
		print(n + 2)


def digitsum(n):
	n = str(n)
	a = []
	for i in n:
		a.append(int(i))
	return sum(a)
for _ in range(int(input())):
	n = int(input())
	k = digitsum(n)
	if k % 2 == 0:
		if digitsum(n + 1) % 2 == 0:
			l = n + 2
		else:
			l = n + 1
	elif digitsum(n + 1) % 2 == 0:
		l = n + 1
	else:
		l = n + 2
	print(l)


def sod(string):
	return sum((int(d) for d in str(string)))
for _ in range(int(input())):
	n = input()
	summ = sod(n)
	num = int(n)
	for x in range(1, 4):
		if summ % 2:
			if sod(num + x) % 2 == 0:
				print(num + x)
				break
		elif sod(num + x) % 2:
			print(num + x)
			break


n = int(input())
for i in range(n):
	n = int(input())
	m = n
	N = n + 1
	i = 0
	while N % 10 == 0:
		i += 1
		N //= 10
	if i % 2 == 0:
		print(m + 1)
	else:
		print(m + 2)


t = int(input())

def digitsum(m):
	p = 0
	for i in range(len(m)):
		p += int(m[i])
	return p
for i in range(t):
	m = input()
	q = digitsum(m)
	while True:
		m = str(int(m) + 1)
		p = digitsum(m)
		if int(q % 2 == 0) != int(p % 2 == 0):
			break
	print(m)


T = int(input())
for _ in range(T):
	N = int(input())
	i = 0
	m = N
	N = N + 1
	while N % 10 == 0:
		i += 1
		N //= 10
	if i % 2 == 0:
		print(m + 1)
	else:
		print(m + 2)


for _ in range(int(input())):
	no = int(input())
	strno = str(no)
	m = no
	no2 = no + 1
	i = 0
	while no2 % 10 == 0:
		i += 1
		no2 = no2 // 10
	if i % 2 == 0:
		print(no + 1)
	else:
		print(no + 2)


for _ in range(int(input())):
	n = int(input())
	ni = 0
	z = n
	while n % 10 == 9:
		ni += 1
		n //= 10
	if ni % 2 != 0:
		print(z + 2)
	else:
		print(z + 1)


from functools import reduce
t = int(input())
for i in range(t):
	a = int(input())
	if a % 100 == 99:
		x = reduce(lambda x, y: int(x) + int(y), str(a))
		y = reduce(lambda x, y: int(x) + int(y), str(a + 1))
		if x % 2 == 0 and y % 2 == 0 or (x % 2 != 0 and y % 2 != 0):
			print(a + 2)
			continue
		print(a + 1)
		continue
	print(a + 1) if a % 10 != 9 else print(a + 2)


def parities(x):
	rem = 0
	while x != 0:
		rem += x % 10
		x //= 10
	if rem % 2 == 0:
		return 1
	elif rem % 2 != 0:
		return 2
t = int(input())
for _ in range(t):
	n = int(input())
	k = parities(n)
	if k == 1:
		while True:
			n += 1
			if parities(n) == 2:
				print(n)
				break
	elif k == 2:
		while True:
			n += 1
			if parities(n) == 1:
				print(n)
				break


def digitsum(ch, n):
	sums = 0
	ch1 = True
	for i in str(n):
		sums += int(i)
	if sums % 2 == 0:
		ch1 = True
	else:
		ch1 = False
	if ch != ch1:
		return n
	else:
		return digitsum(ch, n + 1)
for _ in range(int(input())):
	a = int(input())
	res = 0
	ch = True
	for i in str(a):
		res += int(i)
	if res % 2 == 0:
		ch = True
	else:
		ch = False
	print(digitsum(ch, a + 1))


def digitSum(x):
	sum = 0
	while x > 0:
		sum += x % 10
		x = x // 10
	return sum
for i in range(int(input())):
	n = int(input())
	ans = 0
	num = digitSum(n)
	if num % 2 != 0:
		new = n + 1
		while True:
			flag = digitSum(new)
			if flag % 2 == 0:
				ans = new
				break
			else:
				new = new + 1
	else:
		new = n + 1
		while True:
			flag = digitSum(new)
			if flag % 2 != 0:
				ans = new
				break
			else:
				new = new + 1
	print(ans)


def sumdigits(n):
	sum = 0
	while n:
		sum += n % 10
		n //= 10
	return sum
for i in range(int(input())):
	N = int(input())
	if sumdigits(N) % 2 == 0:
		while True:
			N += 1
			if sumdigits(N) % 2 != 0:
				print(N)
				break
	else:
		while True:
			N += 1
			if sumdigits(N) % 2 == 0:
				print(N)
				break


def digitsum(n):
	s = 0
	for dig in str(n):
		s += int(dig)
	return s

def par(a, b):
	if a % 2 != b % 2:
		return False
	else:
		return True

def findnum():
	n = int(input())
	i = 1
	while True:
		if par(digitsum(n), digitsum(n + i)):
			i += 1
		else:
			return n + i
for t in range(int(input())):
	print(findnum())


def calculatingEven(number, digit, count):
	status = False
	while status == False:
		count = 0
		digit += 1
		for i in str(digit):
			i = int(i)
			count += i
		if count % 2 != 0:
			print(digit)
			status = True

def calculatingOdd(number, digit, count):
	status = True
	while status:
		count = 0
		digit += 1
		string = str(digit)
		for i in string:
			i = int(i)
			count += i
		if count % 2 == 0:
			status = False
	print(digit)
noOfCases = int(input())
for i in range(noOfCases):
	count = 0
	number = input()
	digit = int(number)
	for i in number:
		i = int(i)
		count += i
	if count % 2 == 0:
		calculatingEven(number, digit, count)
	else:
		calculatingOdd(number, digit, count)


t = int(input())
for t in range(t):
	n = int(input())

	def digsum(a):
		sum = 0
		while a > 0:
			sum += a % 10
			a = a // 10
		return sum
	nsum = digsum(n)
	ans = 0
	if nsum % 2 != 0:
		x = n + 1
		while True:
			res = digsum(x)
			if res % 2 == 0:
				ans = x
				break
			else:
				x = x + 1
	else:
		x = n + 1
		while True:
			res = digsum(x)
			if res % 2 != 0:
				ans = x
				break
			else:
				x = x + 1
	print(ans)


def sum_of_digit(number):
	digitsum = 0
	while number > 0:
		lastdigit = number % 10
		digitsum += lastdigit
		number //= 10
	return digitsum

def check_parity(number):
	k = sum_of_digit(number)
	if k % 2 == 0:
		return 'Even'
	return 'Odd'

def next_number(number):
	if check_parity(number) == 'Even':
		while True:
			number = number + 1
			if check_parity(number) == 'Odd':
				return number
	elif check_parity(number) == 'Odd':
		while True:
			number += 1
			if check_parity(number) == 'Even':
				return number

def main():
	for i in range(int(input())):
		k = int(input())
		print(next_number(k))
main()