Count the number of palindromic numbers less than N.
Example 1:
Input:
N = 12
Output:
10
Explanation:
There are 10 palindrome number less than 12.
1 2 3 4 5 6 7 8 9 11
Example 2:
Input:
N = 104
Output:
19
Explanation:
There are 19 palindrome number less than 104.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function palindromicNumbers() which takes an integer N as input parameter and returns the count of the number of the palindromic numbers which are less than N.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^{5}

Difficulty: EASY
Tags: Mathematics
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



class Solution:

    def palindromicNumbers(self, N):

    	#code here 

Solutions:
class Solution:

	def palindromicNumbers(self, N):
		s = []
		count = 0
		for i in range(1, N):
			i = str(i)
			rev = i[::-1]
			if i == rev:
				s.append(i)
				count += 1
		return count


class Solution:

	def palindromicNumbers(self, N):
		a = 0
		for i in range(1, N):
			x = str(i)
			if x == x[::-1]:
				a += 1
		return a


class Solution:

	def palindromicNumbers(self, N):
		c = 0
		for i in range(1, N):
			if str(i) == str(i)[::-1]:
				c += 1
		return c


class Solution:

	def palindromicNumbers(self, N):
		l = []
		for i in range(1, N):
			if str(i) == str(i)[::-1]:
				l.append(i)
		return len(l)


class Solution:

	def palindromicNumbers(self, N):
		import math

		def next_palindrome(num):
			strg = str(num)
			n = len(strg)
			s = set(strg)
			if len(s) == 1 and '9' in s:
				return int('1' + (n - 1) * '0' + '1')
			if n == 1:
				if num == 9:
					return 11
				else:
					return num + 1
			elif math.log(num, 10) == int(math.log(num, 10)):
				return num + 1
			else:
				half = (n + 1) // 2
				first_half = strg[:half]
				if n % 2 == 0:
					n1 = int(first_half + first_half[::-1])
					n2 = 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])
			if n1 > num and n1 <= n2:
				return n1
			else:
				return n2
		start = 1
		count = 0
		while start < N:
			count += 1
			start = next_palindrome(start)
		return count


class Solution:

	def pol(self, st):
		L = int(len(st) / 2)
		arr1 = st[0:L]
		arr2 = st[L:]
		if len(st) % 2 != 0:
			arr2 = st[L + 1:]
		for i in range(0, L):
			if arr1[i] != arr2[L - i - 1]:
				return False
		return True

	def palindromicNumbers(self, N):
		if N < 10:
			return N - 1
		count = 9
		for i in range(10, N):
			st = str(i)
			if self.pol(st):
				count = count + 1
		return count


class Solution:

	def palindromicNumbers(self, N):
		arr = []
		for i in range(1, N):
			x = str(i)
			x = x[::-1]
			if i == int(x):
				arr.append(i)
		return len(arr)


class Solution:

	def palindromicNumbers(self, N):

		def gen(n, base, isEven):
			palin = n
			if not isEven:
				n = n // base
			while n != 0:
				palin = palin * base + n % base
				n = n // base
			return palin
		c = 0
		b = 10
		for v in [True, False]:
			i = 1
			while True:
				p = gen(i, b, v)
				if p >= N:
					break
				c += 1
				i += 1
		return c


class Solution:

	def temp(self, i, is_odd):
		if is_odd:
			n = i // 10
		else:
			n = i
		while n > 0:
			i = i * 10 + n % 10
			n = n // 10
		return i

	def palindromicNumbers(self, N):
		count = 0
		for j in range(2):
			i = 1
			while self.temp(i, j % 2) < N:
				count += 1
				i += 1
		return count


class Solution:

	def palindromicNumbers(self, N):
		arr = []
		for i in range(1, N):
			x = str(i)
			x = x[::-1]
			if i == int(x):
				arr.append(i)
		return len(arr)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		ans = ob.palindromicNumbers(N)
		print(ans)


class Solution:

	def palindromicNumbers(self, N):
		l = list()
		for i in range(1, N):
			j = str(i)
			if int(j) < 10:
				l.append(j)
			elif j[::-1] == j:
				l.append(j)
			else:
				continue
		return len(l)


def _gen_pal(num, way='odd'):
	palin = num
	if way == 'odd':
		num = num // 10
	while num > 0:
		last_digit = num % 10
		palin = palin * 10 + last_digit
		num = num // 10
	return palin

def gen_pal(n):
	odd_vals = []
	even_vals = []
	for i in range(1, n + 1):
		v = _gen_pal(i, 'odd')
		if v >= n:
			break
		odd_vals.append(v)
	for i in range(1, n + 1):
		v = _gen_pal(i, 'even')
		if v >= n:
			break
		even_vals.append(v)
	return len(odd_vals) + len(even_vals)

class Solution:

	def palindromicNumbers(self, N):
		return gen_pal(N)


from math import log

def gen_palindromes(n):
	palins = {}
	for p in range(int(log(n, 10)) + 1):
		if p == 0:
			nums = [elem for elem in range(1, 10) if elem < n]
		elif p == 1:
			nums = []
			for i in range(1, 10):
				elem = i * 10 + i
				if elem >= n:
					break
				nums.append(elem)
		else:
			nums = []
			pwr = 10 ** p
			for i in range(1, 10):
				elem = pwr * i + i
				if elem >= n:
					break
				nums.append(elem)
				for x in range(p % 2, p - 1, 2):
					scale = (p - x) // 2
					for e in palins[x]:
						y = e * 10 ** scale + elem
						if y >= n:
							break
						nums.append(y)
		palins[p] = nums
	ls = []
	for l in palins.values():
		ls.extend(l)
	return len(ls)

class Solution:

	def palindromicNumbers(self, N):
		return gen_palindromes(N)


class Solution:

	def palindromicNumbers(self, N):

		def checkPalindrome(num):
			if num < 10:
				return True
			elif 10 <= num < 100:
				if num % 10 == num // 10:
					return True
			elif 100 <= num < 1000:
				if num % 10 == num // 100:
					return True
			elif 1000 <= num < 10000:
				if num % 10 == num // 1000 and num // 10 % 10 == num // 100 % 10:
					return True
			elif 10000 <= num < 100000:
				if num % 10 == num // 10000 and num // 10 % 10 == num // 1000 % 10:
					return True
			return False
		num_palindrome = 0
		for i in range(1, N):
			if checkPalindrome(i):
				num_palindrome += 1
		return num_palindrome


class Solution:

	def palindromicNumbers(self, N):
		l = []

		def ispal(num):
			num = str(num)
			k = num[::-1]
			if num == k:
				return 1
			return 0
		count = 0
		for i in range(1, N):
			if ispal(i):
				count += 1
		return count


class Solution:

	def palindromicNumbers(self, N):
		m = []
		for i in range(1, N):
			temp = i
			rev = 0
			while i > 0:
				dig = i % 10
				rev = rev * 10 + dig
				i = i // 10
			if temp == rev:
				m.append(rev)
		return len(m)