"""simple docstring"""







from math import sqrt


def      __lowerCAmelCase(		__UpperCAmelCase			):






	"""simple docstring"""





	if 1 < number < 4:
		# 2 and 3 are primes
		return True
	elif number < 2 or number % 2 == 0 or number % 3 == 0:
		# Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
		return False

	# All primes number are in format of 6k +/- 1
	for i in range(5     ,int(sqrt(lowerCAmelCase_			) + 1			)     ,6			):
		if number % i == 0 or number % (i + 2) == 0:
			return False
	return True


def      __lowerCAmelCase(		__UpperCAmelCase = 10_001			):






	"""simple docstring"""





	_lowercase :    List[str]							=							0
	_lowercase :    Tuple							=							1
	while count != nth and number < 3:
		number += 1
		if is_prime(lowerCAmelCase_			):
			count += 1
	while count != nth:
		number += 2
		if is_prime(lowerCAmelCase_			):
			count += 1
	return number


if __name__ == "__main__":
						print(f"""{solution() = }""")




"""simple docstring"""







def      __lowerCAmelCase(		__UpperCAmelCase			):






	"""simple docstring"""





	_lowercase :    str							=							[0 for i in range(len(__UpperCAmelCase			)			)]

	# initialize interval's left pointer and right pointer
	_lowercase				,      _lowercase :    str							=							0, 0

	for i in range(1     ,len(__UpperCAmelCase			)			):
		# case when current index is inside the interval
		if i <= right_pointer:
			_lowercase :    Union[str, Any]							=							min(right_pointer - i + 1     ,z_result[i - left_pointer]			)
			_lowercase :    Any							=							min_edge

		while go_next(__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase			):
			z_result[i] += 1

		# if new index's result gives us more right interval,
		# we've to update left_pointer and right_pointer
		if i + z_result[i] - 1 > right_pointer:
			_lowercase				,      _lowercase :    Optional[int]							=							i, i + z_result[i] - 1

	return z_result


def      __lowerCAmelCase(		__UpperCAmelCase     ,__UpperCAmelCase     ,__UpperCAmelCase			):






	"""simple docstring"""





	return i + z_result[i] < len(__UpperCAmelCase			) and s[z_result[i]] == s[i + z_result[i]]


def      __lowerCAmelCase(		__UpperCAmelCase     ,__UpperCAmelCase			):






	"""simple docstring"""





	_lowercase :    Union[str, Any]							=							0
	# concatenate 'pattern' and 'input_str' and call z_function
	# with concatenated string
	_lowercase :    List[str]							=							z_function(pattern + input_str			)

	for val in z_result:
		# if value is greater then length of the pattern string
		# that means this index is starting position of substring
		# which is equal to pattern string
		if val >= len(__UpperCAmelCase			):
			answer += 1

	return answer


if __name__ == "__main__":
						import doctest

						doctest.testmod()



