




"""simple docstring"""
import timeit







class  _SCREAMING_SNAKE_CASE       :



 '''simple docstring'''





 def __init__(self					,     lowerCAmelCase__   ):

  '''simple docstring'''







  if isinstance(lowerCAmelCase__					,     lowerCAmelCase__   ):  # Initializes a matrix identical to the one provided.
   _UpperCamelCase      :	List[str]					      =  arg
   _UpperCamelCase      :	Tuple					      =  len(lowerCAmelCase__   )
  else:  # Initializes a square matrix of the given size and set values to zero.
   _UpperCamelCase      :	Any					      =  arg
   _UpperCamelCase      :	Union[str, Any]					      =  [[0 for _ in range(self.n   )] for _ in range(self.n   )]






 def __mul__(self					,     lowerCAmelCase__   ):

  '''simple docstring'''







  _UpperCamelCase      :	Optional[int]					      =  Matrix(self.n   )
  for i in range(self.n   ):
   for j in range(self.n   ):
    for k in range(self.n   ):
     matrix.t[i][j] += self.t[i][k] * b.t[k][j]
  return matrix






def 				__lowerCAmelCase					(					__lowerCAmelCase			:		Tuple  ,	__lowerCAmelCase			:		int						)    ->       Tuple:
 _UpperCamelCase      :	str					      =  Matrix([[1, 0], [0, 1]]						)
 while b > 0:
  if b & 1:
   matrix *= a
  a *= a
  b >>= 1
 return matrix






def 				__lowerCAmelCase					(					__lowerCAmelCase			:		str  ,	__lowerCAmelCase			:		Optional[int]  ,	__lowerCAmelCase			:		int						)    ->       Tuple:
 # Trivial Cases
 if n == 1:
  return fa
 elif n == 2:
  return fa
 _UpperCamelCase      :	List[Any]					      =  Matrix([[1, 1], [1, 0]]						)
 _UpperCamelCase      :	str					      =  modular_exponentiation(__lowerCAmelCase  ,	n - 2						)
 return fa * matrix.t[0][0] + fa * matrix.t[0][1]






def 				__lowerCAmelCase					(					__lowerCAmelCase			:		List[str]  ,	__lowerCAmelCase			:		str  ,	__lowerCAmelCase			:		Tuple						)    ->       str:
 # Trivial Cases
 if n == 1:
  return fa
 elif n == 2:
  return fa

 _UpperCamelCase      :	Optional[Any]					      =  fa
 _UpperCamelCase      :	str					      =  fa
 n -= 2

 while n > 0:
  _UpperCamelCase      ,	_UpperCamelCase      :	List[Any]					      =  fn_a + fn_a, fn_a
  n -= 1

 return fn_a






def 				__lowerCAmelCase					(					)    ->       Any:
 _UpperCamelCase      :	List[str]					      =  "\nfrom random import randint\nfrom __main__ import fibonacci_with_matrix_exponentiation\n"
 _UpperCamelCase      :	Union[str, Any]					      =  "fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"
 _UpperCamelCase      :	List[str]					      =  timeit.timeit(setup=__lowerCAmelCase  ,	stmt=__lowerCAmelCase  ,	number=100						)
 print("With matrix exponentiation the average execution time is "  ,	exec_time / 100						)
 return exec_time






def 				__lowerCAmelCase					(					)    ->       Tuple:
 _UpperCamelCase      :	List[str]					      =  "\nfrom random import randint\nfrom __main__ import simple_fibonacci\n"
 _UpperCamelCase      :	List[str]					      =  "simple_fibonacci(randint(1,70000), 1, 1)"
 _UpperCamelCase      :	Optional[int]					      =  timeit.timeit(setup=__lowerCAmelCase  ,	stmt=__lowerCAmelCase  ,	number=100						)
 print(
     "Without matrix exponentiation the average execution time is "  ,	exec_time / 100						)
 return exec_time






def 				__lowerCAmelCase					(					)    ->       Optional[int]:
 matrix_exponentiation_time()
 simple_fibonacci_time()


if __name__ == "__main__":
    main()









"""simple docstring"""
import math






def 				__lowerCAmelCase					(					__lowerCAmelCase			:		Tuple						)    ->       Any:
 _UpperCamelCase      :	str					      =  0
 if n % 2 == 0:
  count += 1
  while n % 2 == 0:
   _UpperCamelCase      :	List[Any]					      =  int(n / 2						)
    # the n input value must be odd so that
    # we can skip one element (ie i += 2)

 _UpperCamelCase      :	Tuple					      =  3

 while i <= int(math.sqrt(__lowerCAmelCase						)						):
  if n % i == 0:
   count += 1
   while n % i == 0:
    _UpperCamelCase      :	Any					      =  int(n / i						)
  _UpperCamelCase      :	Optional[Any]					      =  i + 2

 # this condition checks the prime
 # number n is greater than 2

 if n > 2:
  count += 1
 return count


if __name__ == "__main__":
    _SCREAMING_SNAKE_CASE						 =     5_1_2_4_2_1_8_3
    print(f'The number of distinct prime factors is/are {exact_prime_factor_count(n)}')
    print(f'The value of log(log(n)) is {math.log(math.log(n)):.4f}')



