


import numpy as np


def 				SCREAMING_SNAKE_CASE (     UpperCAmelCase__   ,UpperCAmelCase__="utf-8"   ,UpperCAmelCase__="surrogatepass"							):

				"""simple docstring"""






				_SCREAMING_SNAKE_CASE      = bin(int.from_bytes(text.encode(UpperCAmelCase__   ,UpperCAmelCase__							)   ,'big'							)							)[2:]
				return bits.zfill(8 * ((len(UpperCAmelCase__							) + 7) // 8)							)


def 				SCREAMING_SNAKE_CASE (     UpperCAmelCase__   ,UpperCAmelCase__="utf-8"   ,UpperCAmelCase__="surrogatepass"							):

				"""simple docstring"""






				_SCREAMING_SNAKE_CASE      = int(UpperCAmelCase__   ,2							)
				return n.to_bytes((n.bit_length() + 7) // 8   ,'big'							).decode(UpperCAmelCase__   ,UpperCAmelCase__							) or "\0"


def 				SCREAMING_SNAKE_CASE (     UpperCAmelCase__   ,UpperCAmelCase__							):

				"""simple docstring"""






				if size_par + len(UpperCAmelCase__							) <= 2**size_par - (len(UpperCAmelCase__							) - 1):
								raise ValueError('size of parity don\'t match with size of data'							)

				_SCREAMING_SNAKE_CASE      = []
				_SCREAMING_SNAKE_CASE      = []
				_SCREAMING_SNAKE_CASE      = [bin(UpperCAmelCase__							)[2:] for x in range(1   ,size_par + len(UpperCAmelCase__							) + 1							)]

				# sorted information data for the size of the output data
				_SCREAMING_SNAKE_CASE      = []
				# data position template + parity
				_SCREAMING_SNAKE_CASE      = []
				# parity bit counter
				_SCREAMING_SNAKE_CASE      = 0
				# counter position of data bits
				_SCREAMING_SNAKE_CASE      = 0

				for x in range(1   ,size_par + len(UpperCAmelCase__							) + 1							):
								# Performs a template of bit positions - who should be given,
								# and who should be parity
								if qtd_bp < size_par:
												if (np.log(UpperCAmelCase__							) / np.log(2							)).is_integer():
																data_out_gab.append('P'							)
																_SCREAMING_SNAKE_CASE      = qtd_bp + 1
												else:
																data_out_gab.append('D'							)
								else:
												data_out_gab.append('D'							)

								# Sorts the data to the new output size
								if data_out_gab[-1] == "D":
												data_ord.append(data[cont_data]							)
												cont_data += 1
								else:
												data_ord.append(UpperCAmelCase__							)

    # Calculates parity
				_SCREAMING_SNAKE_CASE      = 0  # parity bit counter
				for bp in range(1   ,size_par + 1							):
								# Bit counter one for a given parity
								_SCREAMING_SNAKE_CASE      = 0
								# counter to control the loop reading
								_SCREAMING_SNAKE_CASE      = 0
								for x in data_ord:
												if x is not None:
																try:
																				_SCREAMING_SNAKE_CASE      = (bin_pos[cont_loop])[-1 * (bp)]
																except IndexError:
																				_SCREAMING_SNAKE_CASE      = '0'
																if aux == "1" and x == "1":
																				cont_bo += 1
												cont_loop += 1
								parity.append(cont_bo % 2							)

								qtd_bp += 1

				# Mount the message
				_SCREAMING_SNAKE_CASE      = 0  # parity bit counter
				for x in range(0   ,size_par + len(UpperCAmelCase__							)							):
								if data_ord[x] is None:
												data_out.append(str(parity[cont_bp]							)							)
												cont_bp += 1
								else:
												data_out.append(data_ord[x]							)

				return data_out


def 				SCREAMING_SNAKE_CASE (     UpperCAmelCase__   ,UpperCAmelCase__							):

				"""simple docstring"""






				_SCREAMING_SNAKE_CASE      = []
				# Parity bit counter
				_SCREAMING_SNAKE_CASE      = 0
				# Counter p data bit reading
				_SCREAMING_SNAKE_CASE      = 0
				# list of parity received
				_SCREAMING_SNAKE_CASE      = []
				_SCREAMING_SNAKE_CASE      = []

				for x in range(1   ,len(UpperCAmelCase__							) + 1							):
								# Performs a template of bit positions - who should be given,
								#  and who should be parity
								if qtd_bp < size_par and (np.log(UpperCAmelCase__							) / np.log(2							)).is_integer():
												data_out_gab.append('P'							)
												_SCREAMING_SNAKE_CASE      = qtd_bp + 1
								else:
												data_out_gab.append('D'							)

								# Sorts the data to the new output size
								if data_out_gab[-1] == "D":
												data_output.append(data[cont_data]							)
								else:
												parity_received.append(data[cont_data]							)
								cont_data += 1

				# -----------calculates the parity with the data
				_SCREAMING_SNAKE_CASE      = []
				_SCREAMING_SNAKE_CASE      = []
				_SCREAMING_SNAKE_CASE      = [bin(UpperCAmelCase__							)[2:] for x in range(1   ,size_par + len(UpperCAmelCase__							) + 1							)]

				#  sorted information data for the size of the output data
				_SCREAMING_SNAKE_CASE      = []
				# Data position feedback + parity
				_SCREAMING_SNAKE_CASE      = []
				# Parity bit counter
				_SCREAMING_SNAKE_CASE      = 0
				# Counter p data bit reading
				_SCREAMING_SNAKE_CASE      = 0

				for x in range(1   ,size_par + len(UpperCAmelCase__							) + 1							):
								# Performs a template position of bits - who should be given,
								# and who should be parity
								if qtd_bp < size_par and (np.log(UpperCAmelCase__							) / np.log(2							)).is_integer():
												data_out_gab.append('P'							)
												_SCREAMING_SNAKE_CASE      = qtd_bp + 1
								else:
												data_out_gab.append('D'							)

								# Sorts the data to the new output size
								if data_out_gab[-1] == "D":
												data_ord.append(data_output[cont_data]							)
												cont_data += 1
								else:
												data_ord.append(UpperCAmelCase__							)

    # Calculates parity
				_SCREAMING_SNAKE_CASE      = 0  # parity bit counter
				for bp in range(1   ,size_par + 1							):
								# Bit counter one for a certain parity
								_SCREAMING_SNAKE_CASE      = 0
								# Counter to control loop reading
								_SCREAMING_SNAKE_CASE      = 0
								for x in data_ord:
												if x is not None:
																try:
																				_SCREAMING_SNAKE_CASE      = (bin_pos[cont_loop])[-1 * (bp)]
																except IndexError:
																				_SCREAMING_SNAKE_CASE      = '0'
																if aux == "1" and x == "1":
																				cont_bo += 1
												cont_loop += 1
								parity.append(str(cont_bo % 2							)							)

								qtd_bp += 1

				# Mount the message
				_SCREAMING_SNAKE_CASE      = 0  # Parity bit counter
				for x in range(0   ,size_par + len(UpperCAmelCase__							)							):
								if data_ord[x] is None:
												data_out.append(str(parity[cont_bp]							)							)
												cont_bp += 1
								else:
												data_out.append(data_ord[x]							)

				_SCREAMING_SNAKE_CASE      = parity_received == parity
				return data_output, ack




from __future__ import annotations

from collections import Counter


def 				SCREAMING_SNAKE_CASE (     UpperCAmelCase__							):

				"""simple docstring"""






				_SCREAMING_SNAKE_CASE      = [True] * n
				_SCREAMING_SNAKE_CASE      = False
				_SCREAMING_SNAKE_CASE      = False
				_SCREAMING_SNAKE_CASE      = True

				for i in range(3   ,int(n**0.5 + 1							)   ,2							):
								_SCREAMING_SNAKE_CASE      = i * 2
								while index < n:
												_SCREAMING_SNAKE_CASE      = False
												_SCREAMING_SNAKE_CASE      = index + i

				_SCREAMING_SNAKE_CASE      = [2]

				for i in range(3   ,UpperCAmelCase__   ,2							):
								if is_prime[i]:
												primes.append(UpperCAmelCase__							)

				return primes


def 				SCREAMING_SNAKE_CASE (     UpperCAmelCase__							):

				"""simple docstring"""






				_SCREAMING_SNAKE_CASE      = str(UpperCAmelCase__							)
				_SCREAMING_SNAKE_CASE      = []
				_SCREAMING_SNAKE_CASE      = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

				for duplicate in Counter(UpperCAmelCase__							) - Counter(set(UpperCAmelCase__							)							):
								_SCREAMING_SNAKE_CASE      = [int(number_str.replace(UpperCAmelCase__   ,UpperCAmelCase__							)							) for digit in digits]
								replacements.append(UpperCAmelCase__							)

				return replacements


def 				SCREAMING_SNAKE_CASE (     UpperCAmelCase__ = 8							):

				"""simple docstring"""






				_SCREAMING_SNAKE_CASE      = set()

				# Filter primes with less than 3 replaceable digits
				_SCREAMING_SNAKE_CASE      = {
				    x for x in set(prime_sieve(100_0000							)							) if len(str(UpperCAmelCase__							)							) - len(set(str(UpperCAmelCase__							)							)							) >= 3
				}

				for prime in primes:
								if prime in numbers_checked:
												continue

								_SCREAMING_SNAKE_CASE      = digit_replacements(UpperCAmelCase__							)

								for family in replacements:
												numbers_checked.update(UpperCAmelCase__							)
												_SCREAMING_SNAKE_CASE      = primes.intersection(UpperCAmelCase__							)

												if len(UpperCAmelCase__							) != family_length:
																continue

												return min(UpperCAmelCase__							)

				return -1


if __name__ == "__main__":
							print(solution())
