


from __future__ import annotations

from collections.abc import Callable
from typing import Generic, TypeVar

__a	 =      TypeVar("""T""")
__a	 =      TypeVar("""U""")






class 	__lowercase					(	Generic[T, U]	):





      def __init__(		self    :       Union[str, Any]       ,							__lowerCamelCase    :       T | None       ,							__lowerCamelCase    :       U | None							)     -> Any:






         """simple docstring"""







         UpperCAmelCase      					=  key
         UpperCAmelCase      					=  val
         UpperCAmelCase      					=  None
         UpperCAmelCase      					=  None





      def __repr__(		self    :       int							)     -> str:






         """simple docstring"""







         return (
             F"""Node: key: {self.key}, val: {self.val}, """
             F"""has next: {bool(self.next							)}, has prev: {bool(self.prev							)}"""
         )






class 	__lowercase					(	Generic[T, U]	):





      def __init__(		self    :       List[str]							)     -> None:






         """simple docstring"""







         UpperCAmelCase      					=  DoubleLinkedListNode(__lowerCamelCase       ,							__lowerCamelCase							)
         UpperCAmelCase      					=  DoubleLinkedListNode(__lowerCamelCase       ,							__lowerCamelCase							)
         UpperCAmelCase					,	UpperCAmelCase      					=  self.rear, self.head





      def __repr__(		self    :       List[str]							)     -> str:






         """simple docstring"""







         UpperCAmelCase      					=  ["""DoubleLinkedList"""]
         UpperCAmelCase      					=  self.head
         while node.next is not None:
            rep.append(str(__lowerCamelCase							)							)
            UpperCAmelCase      					=  node.next
         rep.append(str(self.rear							)							)
         return ",\n    ".join(__lowerCamelCase							)





      def 							_lowercase					(		self    :       Tuple       ,							__lowerCamelCase    :       DoubleLinkedListNode[T, U]							)     -> None:






         """simple docstring"""







         UpperCAmelCase      					=  self.rear.prev

         # All nodes other than self.head are guaranteed to have non-None previous
         assert previous is not None

         UpperCAmelCase      					=  node
         UpperCAmelCase      					=  previous
         UpperCAmelCase      					=  node
         UpperCAmelCase      					=  self.rear





      def 							_lowercase					(		self    :       List[Any]       ,							__lowerCamelCase    :       DoubleLinkedListNode[T, U]							)     -> DoubleLinkedListNode[T, U] | None:






         """simple docstring"""







         if node.prev is None or node.next is None:
            return None

         UpperCAmelCase      					=  node.next
         UpperCAmelCase      					=  node.prev
         UpperCAmelCase      					=  None
         UpperCAmelCase      					=  None
         return node






class 	__lowercase					(	Generic[T, U]	):
      UpperCamelCase										=							{}





      def __init__(		self    :       List[Any]       ,							__lowerCamelCase    :       int							)     -> Optional[Any]:






         """simple docstring"""







         UpperCAmelCase      					=  DoubleLinkedList()
         UpperCAmelCase      					=  capacity
         UpperCAmelCase      					=  0
         UpperCAmelCase      					=  0
         UpperCAmelCase      					=  0
         UpperCAmelCase      					=  {}





      def __repr__(		self    :       Union[str, Any]							)     -> str:






         """simple docstring"""







         return (
             F"""CacheInfo(hits={self.hits}, misses={self.miss}, """
             F"""capacity={self.capacity}, current size={self.num_keys})"""
         )





      def __contains__(		self    :       str       ,							__lowerCamelCase    :       T							)     -> bool:






         """simple docstring"""







         return key in self.cache





      def 							_lowercase					(		self    :       Dict       ,							__lowerCamelCase    :       T							)     -> U | None:






         """simple docstring"""







         if key in self.cache:
            self.hits += 1
            UpperCAmelCase      					=  self.cache[key]
            UpperCAmelCase      					=  self.list.remove(self.cache[key]							)
            assert node == value_node

            # node is guaranteed not None because it is in self.cache
            assert node is not None
            self.list.add(__lowerCamelCase							)
            return node.val
         self.miss += 1
         return None





      def 							_lowercase					(		self    :       Optional[int]       ,							__lowerCamelCase    :       T       ,							__lowerCamelCase    :       U							)     -> None:






         """simple docstring"""







         if key not in self.cache:
            if self.num_keys >= self.capacity:
               # delete first node (oldest) when over capacity
               UpperCAmelCase      					=  self.list.head.next

               # guaranteed to have a non-None first node when num_keys > 0
               # explain to type checker via assertions
               assert first_node is not None
               assert first_node.key is not None
               assert (
                   self.list.remove(__lowerCamelCase							) is not None
               )  # node guaranteed to be in list assert node.key is not None

               del self.cache[first_node.key]
               self.num_keys -= 1
            UpperCAmelCase      					=  DoubleLinkedListNode(__lowerCamelCase       ,							__lowerCamelCase							)
            self.list.add(self.cache[key]							)
            self.num_keys += 1

         else:
            # bump node to the end of the list, update value
            UpperCAmelCase      					=  self.list.remove(self.cache[key]							)
            assert node is not None  # node guaranteed to be in list
            UpperCAmelCase      					=  value
            self.list.add(__lowerCamelCase							)





      @classmethod
      def 							_lowercase					(		cls    :       Optional[Any]       ,							__lowerCamelCase    :       int = 1_2_8							)     -> Callable[[Callable[[T], U]], Callable[..., U]]:






         """simple docstring"""







         def cache_decorator_inner(__lowerCamelCase    :       Callable[[T], U]							) -> Callable[..., U]:
            def cache_decorator_wrapper(*__lowerCamelCase    :       T							) -> U:
               if func not in cls.decorator_function_to_instance_map:
                  UpperCAmelCase      					=  LRUCache(__lowerCamelCase							)

               UpperCAmelCase      					=  cls.decorator_function_to_instance_map[func].get(args[0]							)
               if result is None:
                  UpperCAmelCase      					=  func(*__lowerCamelCase							)
                  cls.decorator_function_to_instance_map[func].put(args[0]       ,							__lowerCamelCase							)
               return result

            def cache_info() -> LRUCache[T, U]:
               return cls.decorator_function_to_instance_map[func]

            setattr(__lowerCamelCase       ,							"""cache_info"""       ,							__lowerCamelCase							)  # noqa: B010

            return cache_decorator_wrapper

         return cache_decorator_inner


if __name__ == "__main__":
 import doctest

 doctest.testmod()







def 	_UpperCamelCase					(    lowerCAmelCase_ )    ->int:
   if n == 1 or not isinstance(lowerCAmelCase_	,    lowerCAmelCase_ ):
      return 0
   elif n == 2:
      return 1
   else:
      UpperCAmelCase      					=  [0, 1]
      for i in range(2	,    n + 1 ):
         sequence.append(sequence[i - 1] + sequence[i - 2] )

      return sequence[n]
def 	_UpperCamelCase					(    lowerCAmelCase_ )    ->int:
   UpperCAmelCase      					=  0
   UpperCAmelCase      					=  2

   while digits < n:
      index += 1
      UpperCAmelCase      					=  len(str(fibonacci(lowerCAmelCase_ ) ) )

   return index
def 	_UpperCamelCase					(    lowerCAmelCase_ = 1_0_0_0 )    ->int:
   return fibonacci_digits_index(lowerCAmelCase_ )


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



