You will be given a positive integer N. Your task is to find the smallest number greater than or equal to N that is a prime and a palindrome.
 
Example 1:
Input: N = 12
Output: 101
Example 2:
Input: N = 4
Output: 5
 
Your Task:
You don't need to read or print anything. Your task is to complete the function PrimePalindrome() which takes N as input parameter and returns the smallest number greater than equal to N that is prime and palindrome.
Expected Time Complexity: O(N)
Expected Space Complexity: O(1)
 
Constraints:
1 <= N <= 10^{6}

Difficulty: EASY
Tags: Number theory

String algorithms
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
	def PrimePalindrome(self, N):
		# Code here

Solutions:
import math

class Solution:

	def is_prime(num):
		count = 0
		for i in range(2, math.floor(math.sqrt(num)) + 1):
			if num % i is 0:
				count += 1
				break
		if count is 0:
			return True
		else:
			return False

	def next_palindrome(num):
		for i in range(1, 10 ** 6):
			s = str(i)
			ans = int(s + s[-2::-1])
			if ans >= num and Solution.is_prime(ans):
				return ans
			s = str(i)
			ans = int(s + s[::-1])
			if ans >= num and Solution.is_prime(ans):
				return ans

	def PrimePalindrome(self, num):
		if num is 1 or num is 4 or num is 6:
			return num + 1
		elif num is 2 or num is 3 or num is 5 or (num is 7):
			return num
		else:
			ans = Solution.next_palindrome(num)
			return ans


import math as mt

def isPrime(num):
	if num < 2 or num % 2 == 0:
		return num == 2
	for i in range(3, mt.ceil(mt.sqrt(num + 1))):
		if num % i == 0:
			return False
	return True

class Solution:

	def PrimePalindrome(self, N):
		if 8 <= N and N <= 11:
			return 11
		for x in range(1, 100000):
			s = str(x)
			d = s[::-1]
			y = int(s + d[1:])
			if y >= N and isPrime(y):
				return y


class Solution:

	def PrimePalindrome(self, N):
		from math import sqrt

		def is_prime(n):
			a = int(sqrt(n))
			if n == 1:
				return 0
			if n == 2:
				return 1
			if n % 2 == 0:
				return 0
			for i in range(3, a + 1, 2):
				if n % i == 0:
					return 0
			return 1

		def is_pali(n):
			n = str(n)
			if n == n[::-1]:
				return 1
			else:
				return 0
		if is_prime(N) and is_pali(N):
			return N
		else:
			for i in range(N + 1, N + 10000000):
				if is_pali(i) and is_prime(i):
					return i


import math

class Solution:

	def nextpalindrome(self, n):
		for i in range(1, 10 ** 6):
			s = str(i)
			ans = int(s + s[-2::-1])
			if ans >= n and self.isprime(ans):
				return ans
			s = str(i)
			ans = int(s + s[::-1])
			if ans >= n and self.isprime(ans):
				return ans

	def isprime(self, n):
		if n < 2:
			return False
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				return False
		return True

	def PrimePalindrome(self, N):
		if N is 1 or N is 4 or N is 6:
			return N + 1
		elif N is 2 or N is 3 or N is 5 or (N is 7):
			return N
		else:
			ans = self.nextpalindrome(N)
			return ans


class Solution:

	def PrimePalindrome(self, N):
		import math

		def prime(a):
			if a == 1 or a == 0:
				return False
			k = int(math.sqrt(a))
			for i in range(2, k + 1):
				if a % i == 0:
					return False
			return True
		for i in range(N, 10000000):
			j = str(i)
			if j == j[::-1]:
				if prime(i):
					return i


class Solution:

	def PrimePalindrome(self, N):

		def isPrime(num):
			if num < 2:
				return False
			div = 2
			while div * div <= num:
				if num % div == 0:
					return False
				div += 1
			return True

		def isPalindrom(N):
			s = str(N)
			rev = s[::-1]
			return s == rev
		while True:
			s = str(N)
			rev = s[::-1]
			if s == rev and isPrime(N):
				return N
			N += 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		N = int(input())
		ob = Solution()
		ans = ob.PrimePalindrome(N)
		print(ans)


class Solution:

	def isprime(self, num):
		if num == 1:
			return False
		for i in range(2, num):
			if num % i == 0:
				return False
		return True

	def PrimePalindrome(self, N):
		i = N
		while True:
			s = str(i)
			if len(s) % 2 == 0:
				v = s[:len(s) // 2]
				n = int(v + v[::-1])
				if n >= N and self.isprime(n):
					return n
			else:
				v = s[:len(s) // 2]
				n = int(v + s[len(s) // 2] + v[::-1])
				if n >= N and self.isprime(n):
					return n
			v = len(s) // 2
			i = (n // 10 ** v + 1) * 10 ** v


class Solution:

	def nextPalindrome(self, N):
		num = [int(x) for x in str(N)]
		n = len(num)
		mid = n // 2
		i = mid - 1
		j = mid + 1 if n % 2 else mid
		leftsmaller = False
		while i >= 0 and num[i] == num[j]:
			i -= 1
			j += 1
		if i < 0 or num[i] < num[j]:
			leftsmaller = True
		while i >= 0:
			num[j] = num[i]
			i -= 1
			j += 1
		if leftsmaller == True:
			carry = 1
			i = mid - 1
			if n % 2 == 0:
				j = mid
			else:
				num[mid] += carry
				carry = 1 if num[mid] == 10 else 0
				num[mid] %= 10
				j = mid + 1
			while i >= 0:
				num[i] = num[i] + carry
				carry = 1 if num[i] == 10 else 0
				num[i] %= 10
				num[j] = num[i]
				i -= 1
				j += 1
		if num[0] == 0:
			num.insert(0, 1)
			num[-1] = 1
		ans = 0
		for i in num:
			ans = ans * 10 + i
		return ans

	def PrimePalindrome(self, N):
		N -= 1
		while True:
			N = self.nextPalindrome(N)
			flag = True
			if N == 1:
				continue
			for i in range(2, N // 2 + 1):
				if N % i == 0:
					flag = False
					break
			if flag:
				return N


def prime(i):
	if i == 1:
		return False
	for j in range(2, int(i ** 0.5) + 1):
		if i % j == 0:
			return False
	return True

class Solution:

	def PrimePalindrome(self, N):
		if 8 <= N and N <= 11:
			return 11
		for i in range(1, 100000):
			x = str(i)
			d = x[-1::-1]
			st = int(x + d[1:])
			if st >= N and prime(st):
				return st