





'''simple docstring'''

import os
import re
import warnings
from shutil import copyfile
from typing import TYPE_CHECKING, Any, Dict, List, Optional, Tuple

import sentencepiece as spm

from ...tokenization_utils import PreTrainedTokenizer


if TYPE_CHECKING:
   from ...tokenization_utils_base import TextInput
from ...utils import logging


UpperCAmelCase					:		Optional[int]		=							logging.get_logger(__name__)

UpperCAmelCase					:		Union[str, Any]		=							{'vocab_file': 'spiece.model'}

UpperCAmelCase					:		Any		=							{
    'vocab_file': {
        't5-small': 'https://huggingface.co/t5-small/resolve/main/spiece.model',
        't5-base': 'https://huggingface.co/t5-base/resolve/main/spiece.model',
        't5-large': 'https://huggingface.co/t5-large/resolve/main/spiece.model',
        't5-3b': 'https://huggingface.co/t5-3b/resolve/main/spiece.model',
        't5-11b': 'https://huggingface.co/t5-11b/resolve/main/spiece.model',
    }
}


# TODO(PVP) - this should be removed in Transformers v5
UpperCAmelCase					:		Union[str, Any]		=							{
    't5-small': 5_1_2,
    't5-base': 5_1_2,
    't5-large': 5_1_2,
    't5-3b': 5_1_2,
    't5-11b': 5_1_2,
}

UpperCAmelCase					:		Tuple		=							'▁'





class lowerCamelCase						(__UpperCAmelCase					):
  _lowercase  :	Tuple       					=				VOCAB_FILES_NAMES
  _lowercase  :	List[Any]       					=				PRETRAINED_VOCAB_FILES_MAP
  _lowercase  :	Any       					=				PRETRAINED_POSITIONAL_EMBEDDINGS_SIZES
  _lowercase  :	Any       					=				["""input_ids""", """attention_mask"""]







  def __init__(		self     ,     lowercase__     ,     lowercase__="</s>"     ,     lowercase__="<unk>"     ,     lowercase__="<pad>"     ,     lowercase__=100     ,     lowercase__=None     ,     lowercase__ = None     ,     lowercase__=True     ,     **lowercase__     ,     )		->						int:






        """simple docstring"""





        if extra_ids > 0 and additional_special_tokens is None:
              _snake_case		:	int					     =     [F'''<extra_id_{i}>''' for i in range(UpperCAmelCase_		)]
        elif extra_ids > 0 and additional_special_tokens is not None:
              # Check that we have the right number of extra_id special tokens
              _snake_case		:	Any					     =     len(set(filter(lambda lowercase__		: bool('''extra_id''' in str(UpperCAmelCase_		)		)     ,     UpperCAmelCase_		)		)		)
              if extra_tokens != extra_ids:
                    raise ValueError(
                        F'''Both extra_ids ({extra_ids}) and additional_special_tokens ({additional_special_tokens}) are'''
                        ''' provided to T5Tokenizer. In this case the additional_special_tokens must include the extra_ids'''
                        ''' tokens'''		)
        if legacy:
              logger.warning_once(
                  F'''You are using the legacy behaviour of the {self.__class__}. This means that tokens that come after special tokens will not be properly handled. We recommend you to'''
                  ''' read the related pull request available at https://github.com/huggingface/transformers/pull/24565'''		)

        _snake_case		:	List[Any]					     =     legacy
        _snake_case		:	List[str]					     =     {} if sp_model_kwargs is None else sp_model_kwargs

        super().__init__(
            eos_token=UpperCAmelCase_     ,     unk_token=UpperCAmelCase_     ,     pad_token=UpperCAmelCase_     ,     extra_ids=UpperCAmelCase_     ,     additional_special_tokens=UpperCAmelCase_     ,     sp_model_kwargs=self.sp_model_kwargs     ,     legacy=UpperCAmelCase_     ,     **UpperCAmelCase_     ,     )

        _snake_case		:	int					     =     vocab_file
        _snake_case		:	List[str]					     =     extra_ids

        _snake_case		:	List[Any]					     =     spm.SentencePieceProcessor(**self.sp_model_kwargs		)
        self.sp_model.Load(UpperCAmelCase_		)







  @staticmethod
  def 				UpperCAmelCase_				(		lowercase__     ,     lowercase__     ,     lowercase__		)		->						List[str]:






        """simple docstring"""





        if pretrained_model_name_or_path in TaTokenizer.max_model_input_sizes:
              _snake_case		:	Tuple					     =     TaTokenizer.max_model_input_sizes[pretrained_model_name_or_path]
              if init_max_model_length is not None and init_max_model_length != max_model_length:
                    return init_max_model_length
              elif init_max_model_length is None:
                    warnings.warn(
                        '''This tokenizer was incorrectly instantiated with a model max length of'''
                        F''' {deprecated_max_model_length} which will be corrected in Transformers v5.\nFor now, this'''
                        ''' behavior is kept to avoid breaking backwards compatibility when padding/encoding with'''
                        ''' `truncation is True`.\n- Be aware that you SHOULD NOT rely on'''
                        F''' {pretrained_model_name_or_path} automatically truncating your input to'''
                        F''' {deprecated_max_model_length} when padding/encoding.\n- If you want to encode/pad to sequences'''
                        F''' longer than {deprecated_max_model_length} you can either instantiate this tokenizer with'''
                        ''' `model_max_length` or pass `max_length` when encoding/padding.\n- To avoid this warning, please'''
                        ''' instantiate this tokenizer with `model_max_length` set to your preferred value.'''     ,     UpperCAmelCase_     ,     )

        return max_model_length







  @property
  def 				UpperCAmelCase_				(		self		)		->						List[Any]:






        """simple docstring"""





        return self.sp_model.get_piece_size() + self._extra_ids







  def 				UpperCAmelCase_				(		self		)		->						Optional[int]:






        """simple docstring"""





        _snake_case		:	Optional[Any]					     =     {self.convert_ids_to_tokens(UpperCAmelCase_		): i for i in range(self.vocab_size		)}
        vocab.update(self.added_tokens_encoder		)
        return vocab







  def 				UpperCAmelCase_				(		self     ,     lowercase__     ,     lowercase__ = None     ,     lowercase__ = False		)		->						Optional[int]:






        """simple docstring"""





        if already_has_special_tokens:
              return super().get_special_tokens_mask(
                  token_ids_a=UpperCAmelCase_     ,     token_ids_a=UpperCAmelCase_     ,     already_has_special_tokens=UpperCAmelCase_		)

        # normal case: some special tokens
        if token_ids_a is None:
              return ([0] * len(UpperCAmelCase_		)) + [1]
        return ([0] * len(UpperCAmelCase_		)) + [1] + ([0] * len(UpperCAmelCase_		)) + [1]







  def 				UpperCAmelCase_				(		self		)		->						Any:






        """simple docstring"""





        return list(
            set(filter(lambda lowercase__		: bool(re.search(r'''<extra_id_\d+>'''     ,     UpperCAmelCase_		)		) is not None     ,     self.additional_special_tokens		)		)		)







  def 				UpperCAmelCase_				(		self		)		->						Optional[int]:






        """simple docstring"""





        return [self._convert_token_to_id(UpperCAmelCase_		) for token in self.get_sentinel_tokens()]







  def 				UpperCAmelCase_				(		self     ,     lowercase__		)		->						Tuple:






        """simple docstring"""





        if len(UpperCAmelCase_		) > 0 and token_ids[-1] == self.eos_token_id:
              warnings.warn(
                  F'''This sequence already has {self.eos_token}. In future versions this behavior may lead to duplicated'''
                  ''' eos tokens being added.'''		)
              return token_ids
        else:
              return token_ids + [self.eos_token_id]







  def 				UpperCAmelCase_				(		self     ,     lowercase__     ,     lowercase__ = None		)		->						Dict:






        """simple docstring"""





        _snake_case		:	Optional[Any]					     =     [self.eos_token_id]

        if token_ids_a is None:
              return len(token_ids_a + eos		) * [0]
        return len(token_ids_a + eos + token_ids_a + eos		) * [0]







  def 				UpperCAmelCase_				(		self     ,     lowercase__     ,     lowercase__ = None		)		->						str:






        """simple docstring"""





        _snake_case		:	Any					     =     self._add_eos_if_not_present(UpperCAmelCase_		)
        if token_ids_a is None:
              return token_ids_a
        else:
              _snake_case		:	List[Any]					     =     self._add_eos_if_not_present(UpperCAmelCase_		)
              return token_ids_a + token_ids_a







  def __getstate__(		self		)		->						Optional[int]:






        """simple docstring"""





        _snake_case		:	Optional[Any]					     =     self.__dict__.copy()
        _snake_case		:	Union[str, Any]					     =     None
        return state







  def __setstate__(		self     ,     lowercase__		)		->						List[Any]:






        """simple docstring"""





        _snake_case		:	Optional[int]					     =     d

        # for backward compatibility
        if not hasattr(self     ,     '''sp_model_kwargs'''		):
              _snake_case		:	int					     =     {}

        _snake_case		:	Optional[Any]					     =     spm.SentencePieceProcessor(**self.sp_model_kwargs		)
        self.sp_model.Load(self.vocab_file		)







  def 				UpperCAmelCase_				(		self     ,     lowercase__     ,     **lowercase__		)		->						Optional[int]:






        """simple docstring"""





        if not self.legacy:
              _snake_case		:	Optional[int]					     =     SPIECE_UNDERLINE + text.replace(UpperCAmelCase_     ,     ''' '''		)
        return super().tokenize(UpperCAmelCase_     ,     **UpperCAmelCase_		)







  def 				UpperCAmelCase_				(		self     ,     lowercase__     ,     **lowercase__		)		->						Any:






        """simple docstring"""





        if not self.legacy:
              _snake_case		:	Tuple					     =     text.startswith(UpperCAmelCase_		)
              if is_first:
                    _snake_case		:	Any					     =     text[1:]

        _snake_case		:	Tuple					     =     self.sp_model.encode(UpperCAmelCase_     ,     out_type=UpperCAmelCase_		)

        if not self.legacy and not is_first and not text.startswith(''' '''		) and tokens[0].startswith(UpperCAmelCase_		):
              _snake_case		:	str					     =     ([tokens[0][1:]] if len(tokens[0]		) > 1 else []) + tokens[1:]
        return tokens







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






        """simple docstring"""





        if token.startswith('''<extra_id_'''		):
              _snake_case		:	List[Any]					     =     re.match(r'''<extra_id_(\d+)>'''     ,     UpperCAmelCase_		)
              _snake_case		:	str					     =     int(match.group(1		)		)
              return self.vocab_size - num - 1
        return self.sp_model.piece_to_id(UpperCAmelCase_		)







  def 				UpperCAmelCase_				(		self     ,     lowercase__		)		->						Any:






        """simple docstring"""





        if index < self.sp_model.get_piece_size():
              _snake_case		:	List[str]					     =     self.sp_model.IdToPiece(UpperCAmelCase_		)
        else:
              _snake_case		:	int					     =     F'''<extra_id_{self.vocab_size - 1 - index}>'''
        return token







  def 				UpperCAmelCase_				(		self     ,     lowercase__		)		->						List[Any]:






        """simple docstring"""





        _snake_case		:	Any					     =     []
        _snake_case		:	Dict					     =     ''''''
        _snake_case		:	Optional[Any]					     =     False
        for token in tokens:
              # make sure that special tokens are not decoded using sentencepiece model
              if token in self.all_special_tokens:
                    if not prev_is_special:
                          out_string += " "
                    out_string += self.sp_model.decode(UpperCAmelCase_		) + token
                    _snake_case		:	Tuple					     =     True
                    _snake_case		:	List[Any]					     =     []
              else:
                    current_sub_tokens.append(UpperCAmelCase_		)
                    _snake_case		:	str					     =     False
        out_string += self.sp_model.decode(UpperCAmelCase_		)
        return out_string.strip()







  def 				UpperCAmelCase_				(		self     ,     lowercase__     ,     lowercase__ = None		)		->						List[Any]:






        """simple docstring"""





        if not os.path.isdir(UpperCAmelCase_		):
              logger.error(F'''Vocabulary path ({save_directory}) should be a directory'''		)
              return
        _snake_case		:	Any					     =     os.path.join(
            UpperCAmelCase_     ,     (filename_prefix + '''-''' if filename_prefix else '''''') + VOCAB_FILES_NAMES['''vocab_file''']		)

        if os.path.abspath(self.vocab_file		) != os.path.abspath(UpperCAmelCase_		) and os.path.isfile(self.vocab_file		):
              copyfile(self.vocab_file     ,     UpperCAmelCase_		)
        elif not os.path.isfile(self.vocab_file		):
              with open(UpperCAmelCase_     ,     '''wb'''		) as fi:
                    _snake_case		:	List[str]					     =     self.sp_model.serialized_model_proto()
                    fi.write(UpperCAmelCase_		)

        return (out_vocab_file,)









'''simple docstring'''

def    _a    (							lowerCAmelCase_	):





      """simple docstring"""



      if n == 1 or not isinstance(lowerCAmelCase_			,      lowerCAmelCase_	):
            return 0
      elif n == 2:
            return 1
      else:
            _snake_case		:	Union[str, Any]					     =     [0, 1]
            for i in range(2			,      n + 1	):
                  sequence.append(sequence[i - 1] + sequence[i - 2]	)

            return sequence[n]




def    _a    (							lowerCAmelCase_	):





      """simple docstring"""



      _snake_case		:	Optional[int]					     =     0
      _snake_case		:	int					     =     2

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

      return index




def    _a    (							lowerCAmelCase_ = 1_000	):





      """simple docstring"""



      return fibonacci_digits_index(lowerCAmelCase_	)


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


