



def  lowerCamelCase_(lowerCamelCase_     , lowerCamelCase_     )			->							List[str]:
						assert x is not None
						assert y is not None

						UpperCAmelCase								=  len(lowerCAmelCase__     )
						UpperCAmelCase								=  len(lowerCAmelCase__     )

						# declaring the array for storing the dp values
						UpperCAmelCase								=  [[0] * (n + 1) for _ in range(m + 1     )]  # noqa: E741

						for i in range(1     , m + 1     ):
												for j in range(1     , n + 1     ):
																		UpperCAmelCase								=  1 if x[i - 1] == y[j - 1] else 0

																		UpperCAmelCase								=  max(l[i - 1][j]     , l[i][j - 1]     , l[i - 1][j - 1] + match     )

						UpperCAmelCase								=  """"""
						UpperCAmelCase								=  m, n
						while i > 0 and j > 0:
												UpperCAmelCase								=  1 if x[i - 1] == y[j - 1] else 0

												if l[i][j] == l[i - 1][j - 1] + match:
																		if match == 1:
																								UpperCAmelCase								=  x[i - 1] + seq
																		i -= 1
																		j -= 1
												elif l[i][j] == l[i - 1][j]:
																		i -= 1
												else:
																		j -= 1

						return l[m][n], seq


if __name__ == "__main__":
		__lowerCamelCase  :				Union[str, Any]					=					'AGGTAB'
		__lowerCamelCase  :				Any					=					'GXTXAYB'
		__lowerCamelCase  :				List[Any]					=					4
		__lowerCamelCase  :				List[str]					=					'GTAB'

		__lowerCamelCase  :				List[Any]					=					longest_common_subsequence(a, b)
		print("len =", ln, ", sub-sequence =", subseq)
		import doctest

		doctest.testmod()








def  lowerCAmelCase_	(lowerCAmelCase__:		int  ):





			"""simple docstring"""


			if n == 1 or not isinstance(lowerCAmelCase__		,						lowerCAmelCase__  ):
						return 0
			elif n == 2:
						return 1
			else:
						UpperCAmelCase_:		Optional[int]							      =     [0, 1]
						for i in range(2		,						n + 1  ):
									sequence.append(sequence[i - 1] + sequence[i - 2]  )

						return sequence[n]







def  lowerCAmelCase_	(lowerCAmelCase__:		int  ):





			"""simple docstring"""


			UpperCAmelCase_:		str							      =     0
			UpperCAmelCase_:		str							      =     2

			while digits < n:
						index += 1
						UpperCAmelCase_:		Union[str, Any]							      =     len(str(fibonacci(lowerCAmelCase__  )  )  )

			return index







def  lowerCAmelCase_	(lowerCAmelCase__:		int = 1_0_0_0  ):





			"""simple docstring"""


			return fibonacci_digits_index(lowerCAmelCase__  )


if __name__ == "__main__":
	print(solution(int(str(input()).strip())))






