





"""simple docstring"""






from functools import lru_cache






def      lowercase__ (					lowerCAmelCase__   :			int			)    ->			set:



			'''simple docstring'''
			a__  :	Union[str, Any]		 =			2
			a__  :	int		 =			set()
			while i * i <= n:
						if n % i:
									i += 1
						else:
									n //= i
									factors.add(lowerCAmelCase__			)
			if n > 1:
						factors.add(lowerCAmelCase__			)
			return factors






@lru_cache
def      lowercase__ (					lowerCAmelCase__   :			int			)    ->			int:



			'''simple docstring'''
			return len(unique_prime_factors(lowerCAmelCase__			)			)






def      lowercase__ (					lowerCAmelCase__   :			list			)    ->			bool:



			'''simple docstring'''
			return len(set(lowerCAmelCase__			)			) in (0, 1)






def      lowercase__ (					lowerCAmelCase__   :			int			)    ->			list:



			'''simple docstring'''
			a__  :	List[str]		 =			2

			while True:
						# Increment each value of a generated range
						a__  :	List[str]		 =			[base + i for i in range(lowerCAmelCase__			)]

						# Run elements through out unique_prime_factors function
						# Append our target number to the end.
						a__  :	str		 =			[upf_len(lowerCAmelCase__			) for x in group]
						checker.append(lowerCAmelCase__			)

						# If all numbers in the list are equal, return the group variable.
						if equality(lowerCAmelCase__			):
									return group

						# Increment our base variable by 1
						base += 1






def      lowercase__ (					lowerCAmelCase__   :			int = 4			)    ->			int:



			'''simple docstring'''
			a__  :	List[str]		 =			run(lowerCAmelCase__			)
			return results[0] if len(lowerCAmelCase__			) else None


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






"""simple docstring"""






from __future__ import annotations






def      lowercase__ (					lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			int			)    ->			tuple[int, int]:



			'''simple docstring'''
			if b == 0:
						return (1, 0)
			((a__) ,	(a__))  :	List[Any]		 =			extended_euclid(lowerCAmelCase__							,			a % b			)
			a__  :	str		 =			a // b
			return (y, x - k * y)






def      lowercase__ (					lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			int			)    ->			int:



			'''simple docstring'''
			((a__) ,	(a__))  :	Tuple		 =			extended_euclid(lowerCAmelCase__							,			lowerCAmelCase__			)
			a__  :	List[str]		 =			na * na
			a__  :	Union[str, Any]		 =			ra * x * na + ra * y * na
			return (n % m + m) % m






def      lowercase__ (					lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			int			)    ->			int:



			'''simple docstring'''
			((a__) ,	(a__))  :	Optional[Any]		 =			extended_euclid(lowerCAmelCase__							,			lowerCAmelCase__			)
			if b < 0:
						a__  :	Optional[int]		 =			(b % n + n) % n
			return b






def      lowercase__ (					lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			int							,			lowerCAmelCase__   :			int			)    ->			int:



			'''simple docstring'''
			a__ ,	a__  :	List[Any]		 =			invert_modulo(lowerCAmelCase__							,			lowerCAmelCase__			), invert_modulo(lowerCAmelCase__							,			lowerCAmelCase__			)
			a__  :	Dict		 =			na * na
			a__  :	Any		 =			ra * x * na + ra * y * na
			return (n % m + m) % m


if __name__ == "__main__":
		from doctest import testmod

		testmod(name='''chinese_remainder_theorem''', verbose=True)
		testmod(name='''chinese_remainder_theorem2''', verbose=True)
		testmod(name='''invert_modulo''', verbose=True)
		testmod(name='''extended_euclid''', verbose=True)