






"""simple docstring"""
def 				snake_case      (   A__	,A__ = False						):
			if n == 2:
						return True
			if not n % 2 or n < 2:
						return False
			if n > 5 and n % 10 not in (1, 3, 7, 9):  # can quickly check last digit
						return False
			if n > 3_31_70_44_06_46_79_88_73_85_96_19_81 and not allow_probable:
						raise ValueError(
						    "Warning: upper bound of deterministic test is exceeded. "
						    "Pass allow_probable=True to allow probabilistic test. "
						    "A return value of True indicates a probable prime."						)
			# array bounds provided by analysis
			UpperCAmelCase_     : List[Any]			     =					[
			    20_47,
			    1_37_36_53,
			    25_32_60_01,
			    32_15_03_17_51,
			    2_15_23_02_89_87_47,
			    3_47_47_49_66_03_83,
			    3_41_55_00_71_72_83_21,
			    1,
			    3_82_51_23_05_65_46_41_30_51,
			    1,
			    1,
			    31_86_65_85_78_34_03_11_51_16_74_61,
			    3_31_70_44_06_46_79_88_73_85_96_19_81,
			]

			UpperCAmelCase_     : int			     =					[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
			for idx, _p in enumerate(A__	,1						):
						if n < _p:
									# then we have our last prime to check
									UpperCAmelCase_     : int			     =					primes[:idx]
									break
			UpperCAmelCase_     ,	UpperCAmelCase_     : Tuple			     =					n - 1, 0
			# break up n -1 into a power of 2 (s) and
			# remaining odd component
			# essentially, solve for d * 2 ** s == n - 1
			while d % 2 == 0:
						d //= 2
						s += 1
			for prime in plist:
						UpperCAmelCase_     : Tuple			     =					False
						for r in range(A__						):
									UpperCAmelCase_     : Optional[Any]			     =					pow(A__	,d * 2**r	,A__						)
									# see article for analysis explanation for m
									if (r == 0 and m == 1) or ((m + 1) % n == 0):
												UpperCAmelCase_     : str			     =					True
												# this loop will not determine compositeness
												break
						if pr:
									continue
						# if pr is False, then the above loop never evaluated to true,
						# and the n MUST be composite
						return False
			return True

def 				snake_case      (   ):
			assert not miller_rabin(5_61						)
			assert miller_rabin(5_63						)
			# 2047

			assert not miller_rabin(83_82_01						)
			assert miller_rabin(83_82_07						)
			# 1_373_653

			assert not miller_rabin(17_31_60_01						)
			assert miller_rabin(17_31_60_17						)
			# 25_326_001

			assert not miller_rabin(30_78_38_66_41						)
			assert miller_rabin(30_78_38_66_53						)
			# 3_215_031_751

			assert not miller_rabin(1_71_30_45_57_48_01						)
			assert miller_rabin(1_71_30_45_57_48_19						)
			# 2_152_302_898_747

			assert not miller_rabin(2_77_97_99_72_83_07						)
			assert miller_rabin(2_77_97_99_72_83_27						)
			# 3_474_749_660_383

			assert not miller_rabin(1_13_85_00_23_90_94_41						)
			assert miller_rabin(1_13_85_00_23_90_95_27						)
			# 341_550_071_728_321

			assert not miller_rabin(1_27_50_41_01_88_48_80_43_51						)
			assert miller_rabin(1_27_50_41_01_88_48_80_43_91						)
			# 3_825_123_056_546_413_051

			assert not miller_rabin(7_96_66_46_44_58_50_77_87_79_18_67						)
			assert miller_rabin(7_96_66_46_44_58_50_77_87_79_19_51						)
			# 318_665_857_834_031_151_167_461

			assert not miller_rabin(55_28_40_67_74_46_64_78_97_66_03_33						)
			assert miller_rabin(55_28_40_67_74_46_64_78_97_66_03_59						)
			# 3_317_044_064_679_887_385_961_981
			# upper limit for probabilistic test


if __name__ == "__main__":
			test_miller_rabin()











"""simple docstring"""
lowerCamelCase_					=      [
    (1000, '''M'''),
    (900, '''CM'''),
    (500, '''D'''),
    (400, '''CD'''),
    (100, '''C'''),
    (90, '''XC'''),
    (50, '''L'''),
    (40, '''XL'''),
    (10, '''X'''),
    (9, '''IX'''),
    (5, '''V'''),
    (4, '''IV'''),
    (1, '''I'''),
]

def 				snake_case      (   A__						):
			UpperCAmelCase_     : List[str]			     =					{"I": 1, "V": 5, "X": 10, "L": 50, "C": 1_00, "D": 5_00, "M": 10_00}
			UpperCAmelCase_     : Optional[Any]			     =					0
			UpperCAmelCase_     : Tuple			     =					0
			while place < len(A__						):
						if (place + 1 < len(A__						)) and (vals[roman[place]] < vals[roman[place + 1]]):
									total += vals[roman[place + 1]] - vals[roman[place]]
									place += 2
						else:
									total += vals[roman[place]]
									place += 1
			return total

def 				snake_case      (   A__						):
			UpperCAmelCase_     : Union[str, Any]			     =					[]
			for arabic, roman in ROMAN:
						((UpperCAmelCase_)     ,	(UpperCAmelCase_))     : str			     =					divmod(A__	,A__						)
						result.append(roman * factor						)
						if number == 0:
									break
			return "".join(A__						)


if __name__ == "__main__":
			import doctest

			doctest.testmod()



