Given a number num, our task is to find the closest Palindrome number whose absolute difference with given number is minimum. If 2 Palindome numbers have same absolute difference from the given number, then find the smaller one.
 
Example 1:
Input: num = 9
Output: 9
Explanation: 9 itself is a palindrome
number.
Example 2:
Input: num = 489
Output: 484
Expnataion: closest palindrome numbers from
489 are 484 and 494. Absolute difference between
489 and 494 is equal to the absolute difference
between 484 and 489 but 484 is smaller than 494.
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function closestPalindrome() which takes num as input parameter and returns the closest palindrome.
 
Expected Time Complexity: O(log_{10}num)
Expected Space Complexity: O(1)
 
Constraints:
1 <= num <= 10^{14}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

	def closestPalindrome(self, num):

		# Code here



Solutions:
import math

class Solution:

	def closestPalindrome(self, n):
		n = int(n)
		if n < 10:
			return n
		elif math.log(n, 10) - int(math.log(n, 10)) == 0:
			return n - 1
		else:
			out = str(n)
			ll = int((len(out) + 1) / 2)
			first_Half = out[:ll]
			if len(out) % 2 == 0:
				n1 = int(first_Half + first_Half[::-1])
				n2 = int(str(int(first_Half) + 1) + str(int(first_Half) + 1)[::-1])
				n3 = int(str(int(first_Half) - 1) + str(int(first_Half) - 1)[::-1])
			else:
				n1 = int(first_Half[:-1] + first_Half[::-1])
				n2 = int(str(int(first_Half) + 1)[:-1] + str(int(first_Half) + 1)[::-1])
				n3 = int(str(int(first_Half) - 1)[:-1] + str(int(first_Half) - 1)[::-1])
			if abs(n - n3) <= abs(n - n1) and abs(n - n3) <= abs(n - n2):
				out = n3
			elif abs(n - n1) <= abs(n - n2):
				out = n1
			else:
				out = n2
			return out


class Solution:

	def split_num(self, n):
		sn = str(n)
		ln = len(sn)
		if ln % 2 == 0:
			return (sn[:ln // 2], '', sn[ln // 2:])
		return (sn[:ln // 2], sn[ln // 2], sn[ln // 2 + 1:])

	def closestPalindrome(self, num):
		n = len(str(num))
		if num <= 9:
			return num
		elif num == 10 ** (n - 1):
			return num - 1
		else:
			(l, m, r) = self.split_num(num)
			(prev, nxt) = (0, 0)
			if m == '':
				if not int(l[::-1]) > int(r):
					prev = int(l + l[::-1])
					l = str(int(l) + 1)
					nxt = int(l + l[::-1])
				else:
					nxt = int(l + l[::-1])
					l = str(int(l) - 1)
					prev = int(l + l[::-1])
			elif not int(l[::-1]) > int(r):
				prev = int(l + m + l[::-1])
				l_m = str(int(l + m) + 1)
				(l, m) = (l_m[:-1], l_m[-1])
				nxt = int(l + m + l[::-1])
			else:
				nxt = int(l + m + l[::-1])
				l_m = str(int(l + m) - 1)
				(l, m) = (l_m[:-1], l_m[-1])
				prev = int(l + m + l[::-1])
			if num - prev <= nxt - num:
				return prev
			return nxt


def calc(a, n, k):
	start = (n - 1) // 2
	if k > 0:
		while start >= 0 and a[start] == '9':
			a[start] = '0'
			a[n - 1 - start] = '0'
			start -= 1
		a[start] = str(int(a[start]) + 1)
		a[n - 1 - start] = a[start]
	else:
		while start >= 0 and a[start] == '0':
			a[start] = '9'
			a[n - 1 - start] = '9'
			start -= 1
		a[start] = str(int(a[start]) - 1)
		a[n - 1 - start] = a[start]
	return int(''.join(a))

class Solution:

	def closestPalindrome(self, num):
		for i in range(1, 14):
			if num == 10 ** i:
				return num - 1
		s = str(num)
		a = [c for c in s]
		n = len(s)
		for i in range(n // 2):
			a[n - 1 - i] = a[i]
		k = 1
		num1 = int(''.join(a))
		if num1 == num:
			return num
		elif num1 > num:
			k = -1
		num2 = calc(a, n, k)
		if abs(num1 - num) < abs(num2 - num) or (abs(num1 - num) == abs(num2 - num) and num1 < num2):
			return num1
		return num2


class Solution:

	def closestPalindrome(self, num):
		if num < 10:
			return num
		d = []
		n = 0
		tn = num
		while tn:
			d.append(str(tn % 10))
			tn = tn // 10
			n += 1
		d = d[::-1]
		st = ''.join(d)
		candidats = []
		candidats.append('9' * (n - 1))
		candidats.append('1' + '0' * (n - 1) + '1')
		prefix = int(st[:(n + 1) // 2])
		for pre in [prefix - 1, prefix, prefix + 1]:
			spre = str(pre)
			if n % 2 == 0:
				candidats.append(spre + spre[::-1])
			else:
				candidats.append(spre + spre[::-1][1:])
		return int(sorted(candidats, key=lambda x: (abs(num - int(x)), int(x)))[0])


import math

class Solution:

	def closestPalindrome(self, num):
		num = int(num)
		if num <= 9:
			return num
		elif math.log(num, 10) - int(math.log(num, 10)) == 0:
			return num - 1
		else:
			ans = str(num)
			n1 = int((len(ans) + 1) / 2)
			first_half = ans[:n1]
			if len(ans) % 2 == 0:
				m1 = int(first_half + first_half[::-1])
				m2 = int(str(int(first_half) + 1) + str(int(first_half) + 1)[::-1])
				m3 = int(str(int(first_half) - 1) + str(int(first_half) - 1)[::-1])
			else:
				m1 = int(first_half[:-1] + first_half[::-1])
				m2 = int(str(int(first_half) + 1)[:-1] + str(int(first_half) + 1)[::-1])
				m3 = int(str(int(first_half) - 1)[:-1] + str(int(first_half) - 1)[::-1])
			if abs(num - m3) <= abs(num - m1) and abs(num - m3) <= abs(num - m2):
				ans = m3
			elif abs(num - m1) <= abs(num - m2):
				ans = m1
			else:
				ans = m2
		return ans


import sys
sys.setrecursionlimit(2000)

class Solution:

	def closestPalindrome(self, num):
		num_str = str(num)
		n = len(num_str)
		ans = 9 if n == 1 else int('9' * (n - 1))
		diff = abs(ans - num)

		def dfs(i, s):
			nonlocal ans, diff
			if i == (n + 1) // 2:
				s += s[:-1][::-1] if n & 1 else s[::-1]
				x = int(s)
				(diff, ans) = min([diff, ans], [abs(num - x), x])
				return
			x = int(num_str[i])
			if i < n // 2 - 1:
				dfs(i + 1, s + str(x))
			else:
				for j in [abs((x - 1 + 10) % 10), x, abs((x + 1) % 10)]:
					dfs(i + 1, s + str(j))
		dfs(0, '')
		return ans


class Solution:

	def closestPalindrome(self, num):
		import math
		num = str(num)
		n = int(num)
		if n < 10:
			return n
		elif math.log(n, 10) - int(math.log(n, 10)) == 0:
			return n - 1
		else:
			out = num
			half = (len(out) + 1) // 2
			first_half = out[:half]
			if len(out) % 2 == 0:
				n1 = int(first_half + first_half[::-1])
				n2 = int(str(int(first_half) + 1) + str(int(first_half) + 1)[::-1])
				n3 = int(str(int(first_half) - 1) + str(int(first_half) - 1)[::-1])
			else:
				n1 = int(first_half[:-1] + first_half[::-1])
				n2 = int(str(int(first_half) + 1)[:-1] + str(int(first_half) + 1)[::-1])
				n3 = int(str(int(first_half) - 1)[:-1] + str(int(first_half) - 1)[::-1])
			if abs(n - n3) <= abs(n - n1) and abs(n - n3) <= abs(n - n2):
				out = n3
			elif abs(n - n1) <= abs(n - n2):
				out = n1
			else:
				out = n2
		return out


class Solution:

	def closestPalindrome(self, num):
		if num < 10:
			return num
		for i in range(15):
			if num == 10 ** i:
				return num - 1

		def ispalindrome(num):
			num = str(num)
			n = len(num)
			for i in range(n // 2):
				if num[i] != num[n - 1 - i]:
					return 0
			return 1
		ori = num
		num = list(str(num))
		n = len(num)
		for i in range(n // 2):
			num[n - 1 - i] = num[i]
		ans = int(''.join(num))
		left = str(int(''.join(num[:(n + 1) // 2])) + 1)
		right = left[::-1]
		right = right[n % 2:]
		ans2 = left + right
		ans2 = int(''.join(ans2))
		left = str(int(''.join(num[:(n + 1) // 2])) - 1)
		right = left[::-1]
		right = right[n % 2:]
		ans3 = left + right
		ans3 = int(''.join(ans3))
		diff1 = abs(ori - ans)
		diff2 = abs(ori - ans2)
		diff3 = abs(ori - ans3)
		mn = 1000000
		if diff2 <= mn:
			mn = diff2
			fin = ans2
		if diff1 <= mn:
			mn = diff1
			fin = ans
		if diff3 <= mn:
			fin = ans3
		return fin


class Solution:

	def ispal(self, num):
		k = num
		num = str(num)
		n = len(num)
		i = 0
		j = n - 1
		while i < j:
			if num[i] != num[j]:
				return False
			i += 1
			j -= 1
		return True

	def closestPalindrome(self, num):
		if num == 10:
			return 9
		if self.ispal(num):
			return num
		x = str(num)
		n = len(x)
		mid = (n + 1) // 2 - 1
		if n % 2 == 0:
			a = x[:mid + 1] + x[:mid + 1][::-1]
		else:
			a = x[:mid + 1] + x[:mid][::-1]
		a = int(a)
		mid = (n + 1) // 2 - 1
		fir = int(x[:mid + 1])
		sec = x[mid + 1:]
		fir += 1
		fir = str(fir)
		if len(fir) == len(sec):
			b = fir + fir[::-1]
		else:
			b = fir + fir[:-1][::-1]
		b = int(b)
		fir = int(x[:mid + 1])
		sec = x[mid + 1:]
		fir -= 1
		fir = str(fir)
		if len(fir) == len(sec):
			c = fir + fir[::-1]
		elif len(fir) > len(sec):
			c = fir + fir[:-1][::-1]
		else:
			c = fir + sec[0] + fir[::-1]
		c = int(c)
		answer = a
		mini = abs(num - a)
		if abs(num - b) < mini:
			mini = abs(num - b)
			answer = b
		elif abs(num - b) == mini:
			answer = min(answer, b)
		if abs(num - c) < mini:
			mini = abs(num - c)
			answer = c
		elif abs(num - c) == mini:
			answer = min(answer, c)
		return answer


from sys import maxsize

class Solution:

	def closestPalindrome(self, s):
		s = str(s)
		if s == s[::-1]:
			return s
		n = len(s)
		if n == 1:
			return s
		if n == 2:
			if s[0] == '1' and s[1] == '0':
				return '9'
		if int(s) > 1 and int(s) % 10 == 0:
			temp = int(s)
			while temp > 1 and temp % 10 == 0:
				temp /= 10
			if temp == 1:
				return int(s) - 1
		if s == '9' * n:
			return str(int(s) + 2)
		if s[0] == '1' and s[-1] == '1':
			if n > 2 and s[1:-1] == '0' * (n - 2) or n == 2:
				return str(int(s) - 2)
		if n % 2 == 0:
			left = s[:(n + 1) // 2]
			right = left[::-1]
			res = left + right
			nleft = str(int(left) - 1)
			nright = nleft[::-1]
			pleft = str(int(left) + 1)
			pright = pleft[::-1]
			res1 = nleft + nright
			res2 = pleft + pright
			arr = [int(res), int(res1), int(res2)]
			arr.sort()
			res = arr.pop(0)
			res1 = arr.pop(0)
			res2 = arr.pop(0)
			diff1 = abs(int(s) - int(res))
			if diff1 == 0:
				diff1 = maxsize
			diff2 = abs(int(s) - int(res1))
			diff3 = abs(int(s) - int(res2))
			if diff1 <= diff2 and diff1 <= diff3:
				return res
			elif diff2 <= diff1 and diff2 <= diff3:
				return res1
			else:
				return res2
		else:
			left = s[:(n + 1) // 2]
			right = left[:-1][::-1]
			res = left + right
			nleft = str(int(left) - 1)
			nright = nleft[:-1][::-1]
			pleft = str(int(left) + 1)
			pright = pleft[:-1][::-1]
			res1 = nleft + nright
			res2 = pleft + pright
			arr = [int(res), int(res1), int(res2)]
			arr.sort()
			res = arr.pop(0)
			res1 = arr.pop(0)
			res2 = arr.pop(0)
			diff1 = abs(int(s) - int(res))
			if diff1 == 0:
				diff1 = maxsize
			diff2 = abs(int(s) - int(res1))
			diff3 = abs(int(s) - int(res2))
			if diff1 <= diff2 and diff1 <= diff3:
				return res
			elif diff2 <= diff1 and diff2 <= diff3:
				return res1
			else:
				return res2


class Solution:

	def closestPalindrome(self, num):
		s = str(num)
		n = len(s)
		if n == 1:
			return num
		if str(num) == str(num)[::-1]:
			return num
		n = len(str(num))
		if num == int('1' + '0' * (n - 1)):
			return int('9' * (n - 1))
		poss = []
		mid = (n + 1) // 2
		prefix = num // 10 ** (n - mid)
		v = [prefix, prefix - 1, prefix + 1]
		for i in v:
			ss = str(i)
			if n % 2:
				ss = ss[0:len(ss) - 1]
			ss = ss[::-1]
			c = str(i) + ss
			poss.append(int(c))
		mini = 10 ** 9
		ans = 10 ** 9
		for c in poss:
			if abs(c - num) < mini:
				mini = abs(c - num)
				ans = c
			elif abs(c - num) == mini:
				ans = min(ans, c)
		return ans


class Solution:

	def closestPalindrome(self, num):
		s = str(num)
		l = []
		for i in range(1, 15):
			if num == 10 ** i:
				return num - 1
		if len(s) % 2 == 0:
			dup = s[::-1]
			if dup == s:
				return s
			elif len(s) == 2:
				s1 = num // 11
				s2 = s1 + 1
				if num - s1 * 11 < s2 * 11 - num:
					return s1 * 11
				else:
					return s2 * 11
			else:
				l = len(s) // 2
				dup1 = s[:l]
				dup2 = s[l:]
				dup3 = dup1[::-1]
				dup4 = dup2[::-1]
				s1 = dup1 + dup3
				if num > int(s1):
					s2 = num + abs(int(s1) - num)
				else:
					s2 = num - abs(int(s1) - num)
				s2 = str(s2)
				dup1 = s2[:l]
				dup3 = dup1[::-1]
				s2 = dup1 + dup3
				if abs(int(s1) - num) > abs(int(s2) - num):
					return s2
				else:
					return s1
		else:
			if len(s) == 1:
				return s
			dup = s[::-1]
			if dup == s:
				return s
			else:
				mid = len(s) // 2
				dup1 = s[:mid]
				dup2 = s[mid + 1:]
				dup3 = dup1[::-1]
				dup4 = dup2[::-1]
				s1 = dup1 + s[mid] + dup3
				if num > int(s1):
					s2 = num + abs(int(s1) - num)
				else:
					s2 = num - abs(int(s1) - num)
				s2 = str(s2)
				dup1 = s2[:mid]
				dup2 = s2[mid + 1:]
				dup3 = dup1[::-1]
				dup4 = dup2[::-1]
				s2 = dup1 + s2[mid] + dup3
				if abs(int(s1) - num) == abs(int(s2) - num):
					return min([s1, s2])
				if abs(int(s1) - num) > abs(int(s2) - num):
					return s2
				else:
					return s1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		num = int(input())
		obj = Solution()
		ans = obj.closestPalindrome(num)
		print(ans)


class Solution:

	def closestPalindrome(self, num):
		if num < 10:
			return num
		d = []
		n = 0
		tn = num
		while tn:
			d.append(str(tn % 10))
			tn = tn // 10
			n += 1
		d = d[::-1]
		st = ''.join(d)
		candidats = []
		candidats.append('9' * (n - 1))
		candidats.append('1' + '0' * (n - 1) + '1')
		prefix = int(st[:(n + 1) // 2])
		for pre in [prefix - 1, prefix, prefix + 1]:
			spre = str(pre)
			if n % 2 == 0:
				candidats.append(spre + spre[::-1])
			else:
				candidats.append(spre + spre[::-1][1:])
		return int(sorted(candidats, key=lambda x: (abs(num - int(x)), int(x)))[0])
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		num = int(input())
		obj = Solution()
		ans = obj.closestPalindrome(num)
		print(ans)


class Solution:

	def closestPalindrome(self, n):
		x = n
		l = []
		while n > 0:
			l.append(n % 10)
			n = n // 10
		l = l[::-1]
		t = l[:]
		n = len(l)
		if n % 2 == 1:
			i = n // 2
			j = i - 1
			i += 1
			while i < n:
				l[i] = l[j]
				i += 1
				j -= 1
			t1 = 0
			t2 = 0
			for i in range(n):
				t1 += l[i] * 10 ** i
			if t1 == x:
				return t1
			elif t1 > x:
				i = n // 2
				while l[i] == 0:
					i -= 1
				if i < 0 or (i == 0 and l[i] == 1):
					t2 = int('9' * (n - 1))
				else:
					l[i] -= 1
					for j in range(i + 1, n // 2 + 1):
						l[j] = 9
					i = n // 2
					j = i - 1
					i += 1
					while i < n:
						l[i] = l[j]
						i += 1
						j -= 1
					for i in range(n):
						t2 += l[i] * 10 ** i
				if abs(x - t1) > abs(x - t2):
					return t2
				elif abs(x - t1) == abs(x - t2):
					return min(t1, t2)
				return t1
			else:
				i = n // 2
				while l[i] == 9:
					i -= 1
				if i < 0:
					t2 = int('1' * (n - 1) + '1')
				else:
					l[i] += 1
					for j in range(i + 1, n // 2 + 1):
						l[j] = 0
					i = n // 2
					j = i - 1
					i += 1
					while i < n:
						l[i] = l[j]
						i += 1
						j -= 1
					for i in range(n):
						t2 += l[i] * 10 ** i
				if abs(x - t1) > abs(x - t2):
					return t2
				elif abs(x - t1) == abs(x - t2):
					return min(t1, t2)
				return t1
		else:
			i = n // 2
			j = i - 1
			while i < n:
				l[i] = l[j]
				i += 1
				j -= 1
			t1 = 0
			t2 = 0
			for i in range(n):
				t1 += l[i] * 10 ** i
			if t1 == x:
				return t1
			elif t1 > x:
				i = n // 2 - 1
				while l[i] == 0:
					i -= 1
				if i < 0 or (i == 0 and l[i] == 1):
					t2 = int('9' * (n - 1))
				else:
					l[i] -= 1
					for j in range(i + 1, n // 2 + 1):
						l[j] = 9
					i = n // 2
					j = i - 1
					while i < n:
						l[i] = l[j]
						i += 1
						j -= 1
					for i in range(n):
						t2 += l[i] * 10 ** i
				if abs(x - t1) > abs(x - t2):
					return t2
				elif abs(x - t1) == abs(x - t2):
					return min(t1, t2)
				return t1
			else:
				i = n // 2 - 1
				while l[i] == 9:
					i -= 1
				if i < 0:
					t2 = int('1' * (n - 1) + '1')
				else:
					l[i] += 1
					for j in range(i + 1, n // 2 + 1):
						l[j] = 0
					i = n // 2
					j = i - 1
					while i < n:
						l[i] = l[j]
						i += 1
						j -= 1
					for i in range(n):
						t2 += l[i] * 10 ** i
				if abs(x - t1) > abs(x - t2):
					return t2
				elif abs(x - t1) == abs(x - t2):
					return min(t1, t2)
				return t1


class Solution:

	def closestPalindrome(self, num):
		num_d = 0
		r_num = 0
		is_power = True
		tmp_num = num
		while tmp_num > 0:
			rem = tmp_num % 10
			r_num = r_num * 10 + rem
			if tmp_num > 1 and rem != 0:
				is_power = False
			tmp_num = tmp_num // 10
			num_d += 1
		if num > 1 and is_power is True:
			return num - 1
		i = 0
		new_num_f = 0
		new_num_r = 0
		base = 1
		while i < num_d // 2:
			new_num_f = new_num_f * 10 + r_num % 10
			new_num_r = r_num % 10 * base + new_num_r
			r_num = r_num // 10
			base *= 10
			i += 1
		if num_d % 2 == 0:
			new_num = new_num_f * base + new_num_r
		else:
			new_num = (new_num_f * 10 + r_num % 10) * base + new_num_r
		if new_num == num:
			return new_num
		a = new_num
		if a < num:
			op = 1
		else:
			op = -1
		if num_d % 2 == 0:
			b = new_num_f + op
			b = b * base + self.get_reverse(b)
		else:
			b = new_num_f * 10 + r_num % 10 + op
			b = b * base + self.get_reverse(b // 10)
		if abs(a - num) == abs(b - num):
			return min(a, b)
		elif abs(a - num) < abs(b - num):
			return a
		else:
			return b

	def get_reverse(self, num):
		r_num = 0
		while num > 0:
			r_num = r_num * 10 + num % 10
			num = num // 10
		return r_num


class Solution:

	def closestPalindrome(self, num):
		digits = 0
		n = num
		while n:
			n //= 10
			digits += 1
		if num < 10:
			return num
		candidate = [pow(10, digits) + 1, pow(10, digits) - 1, pow(10, digits - 1) + 1, pow(10, digits - 1) - 1]
		mid = (digits + 1) // 2
		prefix = num // pow(10, digits - mid)
		v = [prefix - 1, prefix, prefix + 1]
		snum = str(num)
		for i in v:
			postfix = str(i)
			if digits & 1:
				postfix = postfix[:-1]
			postfix = postfix[::-1]
			c = str(i) + postfix
			candidate.append(int(c))
		ans = 0
		diff = float('inf')
		for c in candidate:
			if abs(c - num) < diff:
				ans = c
				diff = abs(c - num)
			elif abs(c - num) == diff:
				ans = min(ans, c)
		return ans


class Solution:

	def closestPalindrome(self, num):
		num = str(num)
		if num == num[::-1]:
			return int(num)
		if len(num) == 1:
			return int(num)
		(l, l1) = ([], [])
		if num.count('1') == 1 and num.count('0') == len(num) - 1:
			return int('9' * num.count('0'))
		for i in num:
			l.append(int(i))
		i = 0
		j = len(l) - 1
		z = 0
		while i < j:
			if l[i] < l[j]:
				l[j] = l[i]
				z = 1
			else:
				l[j] = l[i]
				z = 0
			i = i + 1
			j = j - 1
		l1[:] = l
		if z == 1:
			if len(l1) % 2 == 0:
				x = len(l1) // 2 - 1
				while l1[x] + 1 > 9:
					l1[x] = 0
					x = x - 1
				l1[x] = l1[x] + 1
				i = 0
				j = len(l1) - 1
				while i < j:
					l1[j] = l1[i]
					i = i + 1
					j = j - 1
			else:
				x = len(l1) // 2
				if l1[x] + 1 > 9:
					l1[x] = 0
					x = x - 1
					while l1[x] + 1 > 9:
						l1[x] = 0
						x = x - 1
					l1[x] = l1[x] + 1
					i = 0
					j = len(l1) - 1
					while i < j:
						l1[j] = l1[i]
						i = i + 1
						j = j - 1
				else:
					l1[x] = l1[x] + 1
		elif len(l1) % 2 == 0:
			x = len(l1) // 2 - 1
			while l1[x] - 1 < 0:
				l1[x] = 9
				x = x - 1
			l1[x] = l1[x] - 1
			i = 0
			j = len(l1) - 1
			while i < j:
				l1[j] = l1[i]
				i = i + 1
				j = j - 1
		else:
			x = len(l1) // 2
			if l1[x] - 1 < 0:
				while l1[x] - 1 < 0:
					l1[x] = 9
					x = x - 1
				l1[x] = l1[x] - 1
				i = 0
				j = len(l1) - 1
				while i < j:
					l1[j] = l1[i]
					i = i + 1
					j = j - 1
			else:
				l1[x] = l1[x] - 1
		(num1, num2) = (0, 0)
		for i in l1:
			num2 = num2 * 10 + i
		for i in l:
			num1 = num1 * 10 + i
		if abs(int(num) - num1) < abs(int(num) - num2):
			return num1
		elif abs(int(num) - num1) > abs(int(num) - num2):
			return num2
		else:
			if num1 < num2:
				return num1
			return num2


class Solution:

	def closestPalindrome(self, num):
		if num < 10:
			return num
		ln = 0
		rev = 0
		aux = num
		while aux != 0:
			rev *= 10
			rev += aux % 10
			aux //= 10
			ln += 1
		if num == pow(10, ln - 1):
			return num - 1
		half = ln // 2
		pal1 = pal2 = pal3 = 0
		first = num // pow(10, half)
		digit = first % 10
		if ln % 2 == 1:
			pal1 = pal2 = pal3 = first
			pal1 -= 1
			pal3 += 1
		else:
			pal1 = pal2 = pal3 = first
			pal3 += 1
			pal1 -= 1
		first1 = pal1
		first2 = pal2
		first3 = pal3
		if ln % 2 == 1:
			first1 //= 10
			first2 //= 10
			first3 //= 10
		last1 = last2 = last3 = 0
		for i in range(half):
			last1 *= 10
			last2 *= 10
			last3 *= 10
			last1 += first1 % 10
			last2 += first2 % 10
			last3 += first3 % 10
			first1 //= 10
			first2 //= 10
			first3 //= 10
		pal1 *= pow(10, half)
		pal2 *= pow(10, half)
		pal3 *= pow(10, half)
		pal1 += last1
		pal2 += last2
		pal3 += last3
		dif1 = abs(num - pal1)
		dif2 = abs(num - pal2)
		dif3 = abs(num - pal3)
		if dif1 < dif2:
			if dif1 < dif3:
				return pal1
			elif dif1 > dif3:
				return pal3
			elif pal1 < pal3:
				return pal1
			else:
				return pal3
		elif dif1 > dif2:
			if dif2 < dif3:
				return pal2
			elif dif2 > dif3:
				return pal3
			else:
				return min(pal2, pal3)
		elif dif1 < dif3:
			if pal1 < pal2:
				return pal1
			else:
				return pal2
		elif dif1 > dif3:
			return pal3
		else:
			return min(pal1, pal2, pal3)


class Solution:

	def get(self, num):
		st = str(num)
		st = list(st)
		s = ''
		l = len(st)
		i = l // 2 - 1
		j = l // 2
		if l % 2 != 0:
			i += 1
		while j < l:
			st[j] = st[i]
			j += 1
			i -= 1
		for i in st:
			s += i
		return int(s)

	def closestPalindrome(self, num):
		ans = self.get(num)
		gap = abs(ans - num)
		for i in range(15):
			z = pow(10, i)
			if num - z > 0:
				temp = self.get(num - z)
				if gap >= abs(temp - num):
					if gap == abs(temp - num):
						ans = min(ans, temp)
					else:
						ans = temp
			m = 99999999999999999999999999999999999999999999999999999999
			if num + z < m:
				temp = self.get(num + z)
				if gap >= abs(temp - num):
					if gap == abs(temp - num):
						ans = min(ans, temp)
					else:
						ans = temp
		return ans


class Solution:

	def closestPalindrome(self, num):
		digits = 0
		n = num
		if num < 10:
			return num
		while n:
			digits += 1
			n //= 10
		possible = {pow(10, digits) + 1, pow(10, digits - 1) - 1}
		mid = (digits + 1) // 2
		prefix = num // pow(10, digits - mid)
		outcome = {prefix, prefix - 1, prefix + 1}
		for i in outcome:
			postfix = str(i)
			if digits % 2 != 0:
				postfix = postfix[:-1]
			number = str(i) + postfix[::-1]
			possible.add(int(number))
		diff = num
		ans = pow(10, digits)
		for i in possible:
			if abs(i - num) < diff:
				ans = i
				diff = abs(i - num)
			elif abs(i - num) == diff:
				ans = min(i, ans)
		return ans


class Solution:

	def closestPalindrome(self, num):
		n = num
		if n < 10:
			return n
		elif n == 10:
			return 9
		elif str(n) == str(n)[::-1]:
			return n
		else:
			n_str = str(n)
			left = ''
			extra = ''
			p1 = ''
			p2 = ''
			p3 = ''
			if len(n_str) & 1:
				extra = n_str[len(n_str) // 2]
			left = n_str[:len(n_str) // 2]
			p1 = left + extra + left[::-1]
			if len(n_str) & 1:
				p2 = str(int(left + extra) - 1)
				p2 = p2 + p2[:-1][::-1]
				p3 = str(int(left + extra) + 1)
				p3 = p3 + p3[:-1][::-1]
			else:
				p2 = str(int(left) - 1)
				p2 = p2 + p2[::-1]
				p3 = str(int(left) + 1)
				p3 = p3 + p3[::-1]
			tmp = [[int(p1), abs(int(p1) - n)], [int(p2), abs(int(p2) - n)], [int(p3), abs(int(p3) - n)]]
			tmp.sort()
			tmp.sort(key=lambda x: x[1])
			if str(num - abs(tmp[0][0] - num)) == str(num - abs(tmp[0][0] - num))[::-1]:
				return num - abs(tmp[0][0] - num)
			else:
				return tmp[0][0]


class Solution:

	def closestPalindrome(self, num):
		val = str(num)
		n = len(val)
		dic = {}
		if val == val[::-1]:
			return val
		for i in range(1, 15):
			if int(val) == 10 ** i:
				return int(val) - 1
		v = val[:len(val) // 2]
		rv = v[::-1]
		if n % 2 == 0:
			ans = int(v + rv)
		else:
			ans = int(v + val[len(val) // 2] + rv)
		if ans > num:
			dic[ans - num] = ans
			v = 10 ** (n // 2)
			val = str(int(val) // v - 1)
			if n % 2 == 0:
				ans = int(val + val[::-1])
			else:
				v = val[:-1]
				ans = int(v + val[-1] + v[::-1])
			dic[num - ans] = ans
		else:
			dic[num - ans] = ans
			v = 10 ** (n // 2)
			val = str(int(val) // v + 1)
			if n % 2 == 0:
				ans = int(val + val[::-1])
			else:
				v = val[:-1]
				ans = int(v + val[-1] + v[::-1])
			if ans - num not in dic:
				dic[ans - num] = ans
		a = min(dic.keys())
		return dic[a]


class Solution:

	def closestPalindrome(self, num):

		def makePalindrome(n):
			pn = list(str(n))
			i = 0
			j = len(pn) - 1
			while i < j:
				pn[j] = pn[i]
				j -= 1
				i += 1
			return int(''.join(pn))
		p = makePalindrome(num)
		d1 = abs(num - p)
		for i in range(15):
			n = 10 ** i
			if num > n:
				t = makePalindrome(num - n)
				d2 = abs(num - t)
				if d1 >= d2:
					if d1 == d2:
						p = min(t, p)
					else:
						p = t
			if num + n < 1000000000000000.0:
				t = makePalindrome(num + n)
				d2 = abs(num - t)
				if d1 >= d2:
					if d1 == d2:
						p = min(t, p)
					else:
						p = t
		return p


class Solution:

	def closestPalindrome(self, num):
		s = str(num)
		l = []
		for i in range(1, 15):
			if num == 10 ** i:
				return num - 1
		if len(s) % 2 == 0:
			dup = s[::-1]
			if dup == s:
				return s
			elif len(s) == 2:
				s1 = num // 11
				s2 = s1 + 1
				if num - s1 * 11 < s2 * 11 - num:
					return s1 * 11
				else:
					return s2 * 11
			else:
				l = len(s) // 2
				dup1 = s[:l]
				dup2 = s[l:]
				dup3 = dup1[::-1]
				dup4 = dup2[::-1]
				s1 = dup1 + dup3
				if num > int(s1):
					s2 = num + abs(int(s1) - num)
				else:
					s2 = num - abs(int(s1) - num)
				s2 = str(s2)
				dup1 = s2[:l]
				dup3 = dup1[::-1]
				s2 = dup1 + dup3
				if abs(int(s1) - num) > abs(int(s2) - num):
					return s2
				else:
					return s1
		else:
			if len(s) == 1:
				return s
			dup = s[::-1]
			if dup == s:
				return s
			else:
				mid = len(s) // 2
				dup1 = s[:mid]
				dup2 = s[mid + 1:]
				dup3 = dup1[::-1]
				dup4 = dup2[::-1]
				s1 = dup1 + s[mid] + dup3
				if num > int(s1):
					s2 = num + abs(int(s1) - num)
				else:
					s2 = num - abs(int(s1) - num)
				s2 = str(s2)
				dup1 = s2[:mid]
				dup2 = s2[mid + 1:]
				dup3 = dup1[::-1]
				dup4 = dup2[::-1]
				s2 = dup1 + s2[mid] + dup3
				if abs(int(s1) - num) == abs(int(s2) - num):
					return min([s1, s2])
				if abs(int(s1) - num) > abs(int(s2) - num):
					return s2
				else:
					return s1


class Solution:

	def closestPalindrome(self, num):
		s = str(num)
		l = []
		for i in range(1, 15):
			if num == 10 ** i:
				return num - 1
		if len(s) % 2 == 0:
			cache_ = s[::-1]
			if cache_ == s:
				return s
			elif len(s) == 2:
				s1 = num // 11
				s2 = s1 + 1
				if num - s1 * 11 < s2 * 11 - num:
					return s1 * 11
				else:
					return s2 * 11
			else:
				l = len(s) // 2
				cache_1 = s[:l]
				cache_2 = s[l:]
				cache_3 = cache_1[::-1]
				cache_4 = cache_2[::-1]
				s1 = cache_1 + cache_3
				if num > int(s1):
					s2 = num + abs(int(s1) - num)
					s2 = str(s2)
				else:
					s2 = num - abs(int(s1) - num)
					s2 = str(s2)
				cache_1 = s2[:l]
				cache_3 = cache_1[::-1]
				s2 = cache_1 + cache_3
				if abs(int(s1) - num) > abs(int(s2) - num):
					return s2
				else:
					return s1
		else:
			if len(s) == 1:
				return s
			cache_ = s[::-1]
			if cache_ == s:
				return s
			else:
				mid = len(s) // 2
				cache_1 = s[:mid]
				cache_2 = s[mid + 1:]
				cache_3 = cache_1[::-1]
				cache_4 = cache_2[::-1]
				s1 = cache_1 + s[mid] + cache_3
				if num > int(s1):
					s2 = num + abs(int(s1) - num)
				else:
					s2 = num - abs(int(s1) - num)
				s2 = str(s2)
				cache_1 = s2[:mid]
				cache_2 = s2[mid + 1:]
				cache_3 = cache_1[::-1]
				cache_4 = cache_2[::-1]
				s2 = cache_1 + s2[mid] + cache_3
				if abs(int(s1) - num) == abs(int(s2) - num):
					return min([s1, s2])
				if abs(int(s1) - num) > abs(int(s2) - num):
					return s2
				else:
					return s1


class Solution:

	def closestPalindrome(self, n):
		n = str(n)

		def checkPalindrome(n):
			if n == n[::-1]:
				return True
			return False
		if checkPalindrome(n):
			return n
		if int(n) < 10:
			return str(int(n) - 1)
		if int(n) <= 11:
			return '9'
		mid = len(n) // 2
		halfnum = int(n[:-mid])
		nums = [0] * 3
		for i in [-1, 0, 1]:
			nums[i + 1] = str(halfnum + i)
			nums[i + 1] += nums[i + 1][:mid][::-1]
			nums[i + 1] = int(nums[i + 1])
		if len(str(nums[0])) + 2 == len(n):
			nums[0] = nums[0] * 10 + 9
		diff = [abs(num - int(n)) for num in nums]
		if diff[1] == 0:
			diff[1] = float('inf')
		ind = diff.index(min(diff))
		return str(nums[ind])


class Solution:

	def closestPalindrome(self, num):
		s = str(num)
		n = len(s)
		if n == 1:
			return num

		def sol(s):
			i = 0
			j = n - 1
			while i < j:
				if s[i] == s[j]:
					i += 1
					j -= 1
				else:
					return False
			return True
		if sol(s):
			return num
		ans = []
		if n - 1 > 0:
			ans.append(''.join(['9'] * (n - 1)))
		if n + 1 - 2 > 0:
			ans.append('1' + ''.join(['0'] * (n + 1 - 2)) + '1')
		for dx in (-1, 0, 1):
			a = s[:int((n + 1) / 2)]
			for dx in (-1, 0, 1):
				temp = str(int(a) + dx)
				if n % 2 == 0:
					temp += temp[::-1]
				else:
					temp += temp[:-1][::-1]
				if not temp.startswith('00'):
					ans.append(temp)
		diff = float('inf')
		rans = ''
		for cur in ans:
			if abs(int(cur) - num) < diff:
				diff = abs(int(cur) - num)
				rans = cur
		return rans


class Solution:

	def closestPalindrome(self, num):

		def large(x):
			s = str(x)
			d = len(s)
			if s[:(d + 1) // 2][::-1] > s[(d + 1) // 2 - d % 2:]:
				return int(s[:(d + 1) // 2] + s[:(d + 1) // 2 - d % 2][::-1])
			else:
				g = str(int(s[:(d + 1) // 2]) + 1)
				return int(g + g[:len(g) - d % 2][::-1])

		def small(x):
			s = str(x)
			d = len(s)
			if s[:(d + 1) // 2][::-1] < s[(d + 1) // 2 - d % 2:]:
				return int(s[:(d + 1) // 2] + s[:(d + 1) // 2 - d % 2][::-1])
			else:
				g = str(int(s[:(d + 1) // 2]) - 1)
				return int(g + g[:len(g) - d % 2][::-1])
		if str(num) == str(num)[::-1]:
			return num
		n = str(num)
		if n[0] == '1':
			i = 1
			while i < len(n) and n[i] == '0':
				i += 1
			if i == len(n):
				return num - 1
		(s, l) = (small(num), large(num))
		if num - s <= l - num:
			return s
		return l


class Solution:

	def closestPalindrome(self, num):
		s = list(str(num))
		n = len(s)
		i = 0
		while i < n - i - 1:
			if s[i] != s[n - i - 1]:
				s[n - i - 1] = s[i]
			i += 1
		ans = int(''.join(s))
		(x1, x2) = (int('0' + '9' * (len(s) - 1)), int('9' * len(s)))
		if abs(ans - num) >= abs(num - x1):
			ans = x1
		if abs(ans - num) > abs(num - x2):
			ans = x2
		ss = list(s)
		i = (n - 1) // 2
		while i >= 0 and s[i] == '0':
			s[i] = s[n - i - 1] = '9'
			i -= 1
		if i >= 0:
			s[i] = str(int(s[i]) - 1)
			s[n - i - 1] = s[i]
		x3 = int(''.join(s))
		if abs(ans - num) >= abs(num - x3):
			ans = x3
		s = ss
		i = (n - 1) // 2
		while i >= 0 and s[i] == '9':
			s[i] = s[n - i - 1] = '0'
			i -= 1
		if i >= 0:
			s[i] = str(int(s[i]) + 1)
			s[n - i - 1] = s[i]
		x3 = int(''.join(s))
		if abs(ans - num) > abs(num - x3):
			ans = x3
		i = (n - 1) // 2
		while i >= 0 and s[i] == '9':
			s[i] = s[n - i - 1] = '0'
			i -= 1
		if i >= 0:
			s[i] = str(int(s[i]) + 1)
			s[n - i - 1] = s[i]
		x3 = int(''.join(s))
		if abs(ans - num) > abs(num - x3):
			ans = x3
		return ans


class Solution:

	def closestPalindrome(self, n):
		n = str(n)
		a = pow(10, len(n) - 1) - 1
		b = pow(10, len(n)) + 1
		s = len(n)
		if s % 2 == 0:
			q = s // 2 - 1
		else:
			q = s // 2
		left = int(n[:q + 1])

		def pali(l, e):
			res = l
			if not e:
				l = l // 10
			while l > 0:
				res = res * 10 + l % 10
				l = l // 10
			return res
		ans = []
		ans.append(a)
		ans.append(b)
		ans.append(pali(left + 1, s % 2 == 0))
		ans.append(pali(left - 1, s % 2 == 0))
		ans.append(pali(left, s % 2 == 0))
		a = m = float('inf')
		k = int(n)
		for i in ans:
			if abs(i - k) < a:
				a = abs(i - k)
				m = i
			if abs(i - k) == a:
				m = min(i, m)
		return m


class Solution:

	def closestPalindrome(self, num):
		n = str(num)
		if n[::-1] == n:
			return num
		l = len(n)
		candidates = set((str(10 ** l + 1), str(10 ** (l - 1) - 1)))
		prefix = int(n[:(l + 1) // 2])
		for i in map(str, (prefix - 1, prefix, prefix + 1)):
			candidates.add(i + [i, i[:-1]][l % 2][::-1])
		candidates.discard(n)
		return min(candidates, key=lambda x: (abs(int(x) - int(n)), int(x)))


class Solution:

	def closestPalindrome(self, n):
		n = str(n)

		def ispalin(num):
			l = 0
			h = len(num) - 1
			while l <= h:
				if num[l] != num[h]:
					return False
				l += 1
				h -= 1
			return True
		if ispalin(n):
			return n
		elif n[0] == '1' and int(n[1:]) == 0:
			return int(n) - 1
		else:

			def build_palindrome(base: str, is_even_length=True) -> str:
				if is_even_length:
					return base + ''.join(reversed(base))
				else:
					return base[:-1] + base[-1] + ''.join(reversed(base[:-1]))
			is_n_even = len(n) % 2 == 0
			palindrome_base = int(n[0:len(n) // 2]) if is_n_even else int(n[0:len(n) // 2 + 1])
			is_n_palindrome = build_palindrome(str(palindrome_base), is_n_even) == n
			base_candidates = [palindrome_base - 1, palindrome_base, palindrome_base + 1]
			min_diff = float('inf')
			for base_candidate in base_candidates:
				candidate = int(build_palindrome(str(base_candidate), is_n_even))
				if abs(candidate - int(n)) < min_diff:
					min_diff = abs(candidate - int(n))
					min_base_candidate = str(base_candidate)
			return build_palindrome(min_base_candidate, is_n_even)


class Solution:

	def isPalindrome(self, s, n):
		for i in range(n // 2):
			j = n - i - 1
			if s[i] != s[j]:
				return False
		return True

	def addOne(self, s):
		n = int(s)
		n += 1
		return str(n)

	def subOne(self, s):
		n = int(s)
		n -= 1
		return str(n)

	def closestPalindrome(self, num):
		s = str(num)
		n = len(s)
		if self.isPalindrome(s, n):
			return num
		if s == '1' + '0' * (n - 1):
			return '9' * (n - 1)
		sans = ''
		sans2 = ''
		ans1 = 0
		ans2 = 0
		if n % 2 == 0:
			temp = s[:n // 2]
			sans = temp + temp[::-1]
			ans1 = int(sans)
			if ans1 > num:
				temp = self.subOne(temp)
			else:
				temp = self.addOne(temp)
			sans2 = temp + temp[::-1]
			ans2 = int(sans2)
		else:
			temp = s[:n // 2 + 1]
			sans = temp + temp[::-1][1:]
			ans1 = int(sans)
			if ans1 > num:
				temp = self.subOne(temp)
			else:
				temp = self.addOne(temp)
			sans2 = temp + temp[::-1][1:]
			ans2 = int(sans2)
		if abs(num - ans2) > abs(num - ans1):
			return ans1
		elif abs(num - ans2) == abs(num - ans1):
			return min(ans1, ans2)
		else:
			return ans2


class Solution:

	def closestPalindrome(self, num):
		s = str(num)
		if len(s) == 1:
			return num
		if s == s[::-1]:
			return num
		if str(num - 1) == str(num - 1)[::-1]:
			return num - 1
		if len(s) % 2 == 0:
			t = s[:len(s) // 2]
		else:
			t = s[:len(s) // 2 + 1]
		l = ''
		h = ''
		m = ''
		if len(s) % 2 == 0:
			t = str(int(t) - 1)
			l = t + t[::-1]
			t = str(int(t) + 1)
			m = t + t[::-1]
			t = str(int(t) + 1)
			h = t + t[::-1]
		else:
			t = str(int(t) - 1)
			if len(t) < len(s) // 2 + 1:
				l = t + t[::-1]
			else:
				l = t + t[-2::-1]
			t = str(int(t) + 1)
			m = t + t[-2::-1]
			t = str(int(t) + 1)
			h = t + t[-2::-1]
		if abs(num - int(l)) > abs(num - int(m)):
			if abs(num - int(m)) <= abs(num - int(h)):
				return m
			else:
				return h
		elif abs(num - int(l)) <= abs(num - int(h)):
			return l
		else:
			return h


class Solution:

	def closestPalindrome(self, num):

		def get(n):
			n = str(n)
			t = n[:len(n) // 2]
			if len(n) % 2 == 0:
				t = t + t[::-1]
			else:
				t = t + n[len(n) // 2] + t[::-1]
			return int(t)
		if num < 10:
			return num
		t = num
		ans = get(t)
		max = 10 ** 16
		i = 0
		while t < max:
			t = num + 10 ** i
			if t > max:
				break
			i += 1
			opt = get(t)
			if abs(ans - num) > abs(opt - num):
				ans = opt
			if abs(opt - num) == abs(ans - num):
				ans = min(ans, opt)
		t = num
		i = 0
		while t > 0:
			t = num - 10 ** i
			if t < 0:
				break
			i += 1
			opt = get(t)
			if abs(ans - num) > abs(opt - num):
				ans = opt
			if abs(opt - num) == abs(ans - num):
				ans = min(ans, opt)
		return ans


from math import log10

class Solution:

	def closestPalindrome(self, num):

		def reflect(firsthalf):
			l = str(firsthalf)
			return l + l[:-(N % 2) or None][::-1]
		num = str(num)
		if num == num[::-1]:
			return num
		(N, n) = (len(num), int(num))
		if N == 1:
			return n
		elif log10(n).is_integer() or log10(n - 1).is_integer():
			return int((N - 1) * '9')
		elif log10(n + 1).is_integer():
			return int('1' + '0' * (N - 1) + '1')
		lefthalf = int(str(n)[:(N + 1) // 2])
		lefthalfuppered = lefthalf + 1
		lefthalflowered = lefthalf - 1
		return int(min(map(reflect, (lefthalflowered, lefthalf, lefthalfuppered)), key=lambda num: abs(n - int(num)) or float('inf')))


class Solution:

	def closestPalindrome(self, num):

		def returnPalindrome(n, isodd):
			s = str(n)
			i = len(s) - 1
			if isodd:
				i -= 1
			while i >= 0:
				s += s[i]
				i -= 1
			return int(s)

		def is_10_pow(n):
			if n == 1:
				return True
			elif n == 0 or n % 10 != 0:
				return False
			return is_10_pow(n // 10)
		if num <= 9:
			return num
		if is_10_pow(num):
			return num - 1
		s = str(num)
		n = len(s)
		isodd = n & 1
		new_s = ''
		if isodd:
			m = n // 2 + 1
		else:
			m = n // 2
		for i in range(m):
			new_s += s[i]
		new_num = int(new_s)
		ans = returnPalindrome(new_num, isodd)
		ans1 = returnPalindrome(new_num - 1, isodd)
		ans2 = returnPalindrome(new_num + 1, isodd)
		if abs(ans - num) >= abs(ans1 - num):
			ans = ans1
		if abs(ans - num) > abs(ans2 - num):
			ans = ans2
		return ans


import math

class Solution:

	def closestPalindrome(self, n):
		if n < 10:
			return n
		elif math.log(n, 10) - int(math.log(n, 10)) == 0:
			return n - 1
		else:
			n_str = str(n)
			l1 = int((len(n_str) + 1) / 2)
			fH = n_str[:l1]
			if len(n_str) % 2 == 0:
				n1 = int(fH + fH[::-1])
				n2 = int(str(int(fH) + 1) + str(int(fH) + 1)[::-1])
				n3 = int(str(int(fH) - 1) + str(int(fH) - 1)[::-1])
			else:
				n1 = int(fH[:-1] + fH[::-1])
				n2 = int(str(int(fH) + 1)[:-1] + str(int(fH) + 1)[::-1])
				n3 = int(str(int(fH) - 1)[:-1] + str(int(fH) - 1)[::-1])
		if abs(n - n3) <= abs(n - n1) and abs(n - n3) <= abs(n - n2):
			n_str = n3
		elif abs(n - n1) <= abs(n - n2):
			n_str = n1
		else:
			n_str = n2
		return n_str


class Solution:

	def closestPalindrome(self, num):
		k = str(num)
		if len(k) == 1 or k == k[::-1]:
			return num
		(maxLen, N) = (len(k), num)
		(low, high) = (10 ** (maxLen - 1) - 1, 10 ** maxLen + 1)
		isOddLen = maxLen & 1
		firstHalf = int(k[:(maxLen >> 1) + isOddLen])
		smaller = int(str(firstHalf - 1) + str(firstHalf - 1)[-1 - isOddLen::-1])
		same = int(str(firstHalf) + str(firstHalf)[-1 - isOddLen::-1])
		larger = int(str(firstHalf + 1) + str(firstHalf + 1)[-1 - isOddLen::-1])
		if same == N:
			return str(min([low, high, smaller, larger], key=lambda x: (abs(x - N), x)))
		else:
			return str(min([low, high, smaller, same, larger], key=lambda x: (abs(x - N), x)))


class Solution:

	def closestPalindrome(self, num):
		num = str(num)
		l = len(num)
		if l < 2:
			return num
		if num == num[::-1]:
			return num
		if num == '1' + '0' * (l - 1):
			return '9' * (l - 1)
		odd = int(l % 2 == 1)
		pal = num[:l // 2 + odd]

		def palindrome(pal, odd):
			if odd:
				palx = pal[:-1]
				return pal + palx[::-1]
			return pal + pal[::-1]
		res = palindrome(pal, odd)
		x = palindrome(str(int(pal) + 1), odd)
		if abs(int(res) - int(num)) > abs(int(x) - int(num)):
			res = x
		x = palindrome(str(int(pal) - 1), odd)
		if abs(int(res) - int(num)) >= abs(int(x) - int(num)):
			res = x
		return res


class Solution:

	def closestPalindrome(self, num):
		if num <= 9:
			return num
		length = len(str(num))
		if num == 10 ** (length - 1):
			return 10 ** (length - 1) - 1

		def make_palin(s):
			return int(s + s[length // 2 - 1::-1])
		half2 = str(num)[:(length + 1) // 2]
		pal2 = make_palin(half2)
		ans = pal2
		if int(half2) != 10 ** (len(half2) - 1):
			half1 = str(int(half2) - 1)
			pal1 = make_palin(half1)
			if abs(pal1 - num) <= abs(pal2 - num):
				ans = pal1
		if not all((ch == '9' for ch in half2)):
			half3 = str(int(half2) + 1)
			pal3 = make_palin(half3)
			if abs(pal3 - num) < abs(pal2 - num):
				ans = pal3
		return ans


class Solution:

	def is_palindrome(self, num_str):
		if num_str == num_str[::-1]:
			return True
		return False

	def closestPalindrome(self, num):
		if num < 10:
			return num
		num_str = str(num)
		if int(num_str[1:]) == 0 and num_str[0] == '1':
			return num - 1
		if self.is_palindrome(num_str):
			return num
		p = []
		num_str = str(num)
		l = len(num_str)
		if l % 2 == 1:
			middle = l // 2
			left = num_str[0:middle]
			if num_str[l // 2] == '0':
				temp_left = str(int(left) - 1)
				p.append(temp_left + '9' + temp_left[::-1])
			else:
				p.append(left + str(int(num_str[l // 2]) - 1) + left[::-1])
			p.append(left + num_str[l // 2] + left[::-1])
			if num_str[l // 2] == '9':
				temp_left = str(int(left) + 1)
				p.append(temp_left + '0' + temp_left[::-1])
			else:
				p.append(left + str(int(num_str[l // 2]) + 1) + left[::-1])
		else:
			middle = l // 2
			left = num_str[0:middle]
			if left[middle - 1] == '0':
				temp_left = str(int(left[0:middle - 1]) - 1) + '9'
			else:
				temp_left = left[0:middle - 1] + str(int(left[middle - 1]) - 1)
			p.append(temp_left + temp_left[::-1])
			p.append(left + left[::-1])
			if left[middle - 1] == '9':
				if middle - 1 == 0:
					temp_left = '10'
				else:
					temp_left = str(int(left[0:middle - 1]) + 1) + '0'
			else:
				temp_left = left[0:middle - 1] + str(int(left[middle - 1]) + 1)
			p.append(temp_left + temp_left[::-1])
		diff = []
		diff.append(abs(num - int(p[0])))
		diff.append(abs(num - int(p[1])))
		diff.append(abs(num - int(p[2])))
		min_index = 0
		for index in range(1, 3):
			if diff[index] < diff[min_index]:
				min_index = index
		return int(p[min_index])


class Solution:

	def closestPalindrome(self, S):
		S = str(S)
		if S == S[::-1]:
			return S
		K = len(S)
		candidates = [str(10 ** k + d) for k in (K - 1, K) for d in (-1, 1)]
		prefix = S[:(K + 1) // 2]
		P = int(prefix)
		for start in map(str, (P - 1, P, P + 1)):
			candidates.append(start + (start[:-1] if K % 2 else start)[::-1])

		def delta(x):
			return abs(int(S) - int(x))
		ans = None
		for cand in candidates:
			if cand != S and (not cand.startswith('00')):
				if ans is None or delta(cand) < delta(ans) or (delta(cand) == delta(ans) and int(cand) <= int(ans)):
					ans = cand
		return ans


class Solution:

	def getPalindrome(self, left, odd):
		S = str(left)
		n = len(S)
		return int(S[:n - odd] + S[::-1])

	def closestPalindrome(self, num):
		if num == 0:
			return 0
		S = str(num)
		n = len(S)
		left = int(S[:(n + 1) // 2])
		cand = [self.getPalindrome(left - 1, n % 2), self.getPalindrome(left, n % 2), self.getPalindrome(left + 1, n % 2), 10 ** (n - 1) - 1, 10 ** (n + 1) + 1]
		return min(((abs(x - num), x) for x in cand))[1]


class Solution:

	def buildPalindrome(self, string, l):
		return (string[:-1] + string[-1] + string[:-1][::-1], string + string[::-1])

	def closestPalindrome(self, num):
		if num < 10:
			return num
		str_num = str(num)
		l = len(str_num)
		mid = (l - 1) // 2
		left_part = str_num[:mid + 1]
		m = int(left_part)
		result = -1
		min_diff = float('inf')
		for option in [m + 1, m, m - 1]:
			options = self.buildPalindrome(str(option), l)
			for str_option in options:
				int_option = int(str_option)
				if int_option == 0:
					int_option = 9
				diff = abs(int_option - num)
				if diff <= min_diff:
					if diff == min_diff:
						if int_option < result:
							result = int_option
					else:
						result = int_option
						min_diff = diff
		return result


class Solution:

	def is_palin(self, n: str):
		for i in range(len(n) // 2):
			if n[i] != n[len(n) - 1 - i]:
				return False
		return True

	def closestPalindrome(self, num: int):
		if num == 10:
			return 9
		if num == 0:
			return 0
		x1 = [int(a) for a in str(num)]
		for i in range(0, len(x1) // 2):
			x1[-1 - i] = x1[i]
		y = ''
		for i in x1:
			y += str(i)
		x1 = int(y)
		x2 = str(num)
		tmp = 0
		if x1 >= num:
			tmp = int(x2) - 1 * 10 ** (len(x2) // 2)
		else:
			tmp = int(x2) + 1 * 10 ** (len(x2) // 2)
		tmp1 = [int(a) for a in str(tmp)]
		for i in range(len(tmp1) // 2):
			tmp1[len(tmp1) - 1 - i] = tmp1[i]
		tmp2 = ''
		for i in tmp1:
			tmp2 += str(i)
		x2 = int(tmp2)
		if abs(x1 - num) > abs(x2 - num):
			return x2
		elif abs(x1 - num) == abs(x2 - num):
			if x1 > num:
				return x2
			return x1
		else:
			return x1