


'''simple docstring'''

def __UpperCamelCase (      __lowerCamelCase		:			int   ,	__lowerCamelCase		:			int					)   ->  int:







     '''simple docstring'''






     if a < b:
          return gcd(__lowerCamelCase   ,	__lowerCamelCase					)
     if a % b == 0:
          return b
     return gcd(__lowerCamelCase   ,	a % b					)






def __UpperCamelCase (      __lowerCamelCase		:			int   ,	__lowerCamelCase		:			int   ,	__lowerCamelCase		:			int					)   ->  int:







     '''simple docstring'''






     if y == 0:
          return 1
     _a            =		power(__lowerCamelCase   ,	y // 2   ,	__lowerCamelCase					) % mod
     _a            =		(temp * temp) % mod
     if y % 2 == 1:
          _a            =		(temp * x) % mod
     return temp






def __UpperCamelCase (      __lowerCamelCase		:			int					)   ->  bool:







     '''simple docstring'''






     _a            =		2
     while b < n:
          if gcd(__lowerCamelCase   ,	__lowerCamelCase					) == 1 and power(__lowerCamelCase   ,	n - 1   ,	__lowerCamelCase					) != 1:
               return False
          b += 1
     return True


if __name__ == "__main__":
   lowercase__					  =		int(input("Enter number: ").strip())
   if is_carmichael_number(number):
      print(f'''{number} is a Carmichael Number.''')
   else:
      print(f'''{number} is not a Carmichael Number.''')





'''simple docstring'''

def __UpperCamelCase (      __lowerCamelCase		:			int					)   ->  int:







     '''simple docstring'''






     if not isinstance(__lowerCamelCase   ,	__lowerCamelCase					) or number < 0:
          raise ValueError("Input must be a non-negative integer"					)

     _a            =		number & ~(number - 1)
     _a            =		0
     while intermediate:
          intermediate >>= 1
          index += 1
     return index - 1


if __name__ == "__main__":
   import doctest

   doctest.testmod(verbose=True)

