




import inspect
import unittest
from typing import List

import numpy as np

from transformers import EfficientFormerConfig
from transformers.testing_utils import require_tf, require_vision, slow
from transformers.utils import cached_property, is_tf_available, is_vision_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_tf_common import TFModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_tf_available():
  import tensorflow as tf

  from transformers import (
      TFEfficientFormerForImageClassification,
      TFEfficientFormerForImageClassificationWithTeacher,
      TFEfficientFormerModel,
  )
  from transformers.models.efficientformer.modeling_tf_efficientformer import (
      TF_EFFICIENTFORMER_PRETRAINED_MODEL_ARCHIVE_LIST,
  )


if is_vision_available():
  from PIL import Image

  from transformers import EfficientFormerImageProcessor


class 				UpperCamelCase_    :

    '''simple docstring'''






    def __init__(			self      :	Tuple					, UpperCAmelCase__      :	Union[str, Any]					, UpperCAmelCase__      :	Union[str, Any] = 13					, UpperCAmelCase__      :	Tuple = 64					, UpperCAmelCase__      :	int = 2					, UpperCAmelCase__      :	Any = 3					, UpperCAmelCase__      :	str = 3					, UpperCAmelCase__      :	Tuple = True					, UpperCAmelCase__      :	int = True					, UpperCAmelCase__      :	List[str] = 128					, UpperCAmelCase__      :	Union[str, Any]=[16, 32, 64, 128]					, UpperCAmelCase__      :	int = 7					, UpperCAmelCase__      :	Optional[Any] = 4					, UpperCAmelCase__      :	List[Any] = 37					, UpperCAmelCase__      :	Optional[Any] = "gelu"					, UpperCAmelCase__      :	Optional[Any] = 0.1					, UpperCAmelCase__      :	str = 0.1					, UpperCAmelCase__      :	Optional[int] = 10					, UpperCAmelCase__      :	Any = 0.02					, UpperCAmelCase__      :	str = 2					, UpperCAmelCase__      :	Optional[Any] = 1					, UpperCAmelCase__      :	Optional[int] = 128					, UpperCAmelCase__      :	List[Any] = [2, 2, 2, 2]					, UpperCAmelCase__      :	Any = 2					, UpperCAmelCase__      :	Tuple = 2					, )						->Union[str, Any]:





           '''simple docstring'''

           A__       =    parent
           A__       =    batch_size
           A__       =    image_size
           A__       =    patch_size
           A__       =    num_channels
           A__       =    is_training
           A__       =    use_labels
           A__       =    hidden_size
           A__       =    num_hidden_layers
           A__       =    num_attention_heads
           A__       =    intermediate_size
           A__       =    hidden_act
           A__       =    hidden_dropout_prob
           A__       =    attention_probs_dropout_prob
           A__       =    type_sequence_label_size
           A__       =    initializer_range
           A__       =    encoder_stride
           A__       =    num_attention_outputs
           A__       =    embed_dim
           A__       =    embed_dim + 1
           A__       =    resolution
           A__       =    depths
           A__       =    hidden_sizes
           A__       =    dim
           A__       =    mlp_expansion_ratio


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





           '''simple docstring'''

           A__       =    floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size])

           A__       =    None
           if self.use_labels:
                  A__       =    ids_tensor([self.batch_size]					, self.type_sequence_label_size)

           A__       =    self.get_config()

           return config, pixel_values, labels


    def        SCREAMING_SNAKE_CASE							(			self      :	List[Any])						->List[str]:





           '''simple docstring'''

           return EfficientFormerConfig(
               image_size=self.image_size					, patch_size=self.patch_size					, num_channels=self.num_channels					, hidden_size=self.hidden_size					, num_hidden_layers=self.num_hidden_layers					, num_attention_heads=self.num_attention_heads					, intermediate_size=self.intermediate_size					, hidden_act=self.hidden_act					, hidden_dropout_prob=self.hidden_dropout_prob					, attention_probs_dropout_prob=self.attention_probs_dropout_prob					, is_decoder=_SCREAMING_SNAKE_CASE					, initializer_range=self.initializer_range					, encoder_stride=self.encoder_stride					, resolution=self.resolution					, depths=self.depths					, hidden_sizes=self.hidden_sizes					, dim=self.dim					, mlp_expansion_ratio=self.mlp_expansion_ratio					, )


    def        SCREAMING_SNAKE_CASE							(			self      :	int					, UpperCAmelCase__      :	int					, UpperCAmelCase__      :	Dict					, UpperCAmelCase__      :	List[Any])						->Union[str, Any]:





           '''simple docstring'''

           A__       =    TFEfficientFormerModel(config=_SCREAMING_SNAKE_CASE)
           A__       =    model(_SCREAMING_SNAKE_CASE					, training=_SCREAMING_SNAKE_CASE)
           self.parent.assertEqual(result.last_hidden_state.shape					, (self.batch_size, self.seq_length, self.hidden_size))


    def        SCREAMING_SNAKE_CASE							(			self      :	Tuple					, UpperCAmelCase__      :	int					, UpperCAmelCase__      :	Optional[Any]					, UpperCAmelCase__      :	Dict)						->Dict:





           '''simple docstring'''

           A__       =    self.type_sequence_label_size
           A__       =    TFEfficientFormerForImageClassification(_SCREAMING_SNAKE_CASE)
           A__       =    model(_SCREAMING_SNAKE_CASE					, labels=_SCREAMING_SNAKE_CASE					, training=_SCREAMING_SNAKE_CASE)
           self.parent.assertEqual(result.logits.shape					, (self.batch_size, self.type_sequence_label_size))

           # test greyscale images
           A__       =    1
           A__       =    TFEfficientFormerForImageClassification(_SCREAMING_SNAKE_CASE)

           A__       =    floats_tensor([self.batch_size, 1, self.image_size, self.image_size])
           A__       =    model(_SCREAMING_SNAKE_CASE					, labels=_SCREAMING_SNAKE_CASE)
           self.parent.assertEqual(result.logits.shape					, (self.batch_size, self.type_sequence_label_size))





    def        SCREAMING_SNAKE_CASE							(			self      :	str)						->Dict:





           '''simple docstring'''

           A__       =    self.prepare_config_and_inputs()
           A__       =    config_and_inputs
           A__       =    {"""pixel_values""": pixel_values}
           return config, inputs_dict


@require_tf
class 				UpperCamelCase_    ( UpperCAmelCase__		,					UpperCAmelCase__		,					unittest.TestCase     ):

    '''simple docstring'''






    UpperCAmelCase__							  =      (
        (
            TFEfficientFormerModel,
            TFEfficientFormerForImageClassificationWithTeacher,
            TFEfficientFormerForImageClassification,
        )
        if is_tf_available()
        else ()
    )
    UpperCAmelCase__							  =      (
        {
            'feature-extraction': TFEfficientFormerModel,
            'image-classification': (
                TFEfficientFormerForImageClassification,
                TFEfficientFormerForImageClassificationWithTeacher,
            ),
        }
        if is_tf_available()
        else {}
    )

    UpperCAmelCase__							  =      False

    UpperCAmelCase__							  =      False
    UpperCAmelCase__							  =      False
    UpperCAmelCase__							  =      False
    UpperCAmelCase__							  =      False


    def        SCREAMING_SNAKE_CASE							(			self      :	Optional[Any])						->Any:





           '''simple docstring'''

           A__       =    TFEfficientFormerModelTester(self)
           A__       =    ConfigTester(
               self					, config_class=_SCREAMING_SNAKE_CASE					, has_text_modality=_SCREAMING_SNAKE_CASE					, hidden_size=37)


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





           '''simple docstring'''

           self.config_tester.run_common_tests()


    @unittest.skip(reason='''EfficientFormer does not use inputs_embeds''')
    def        SCREAMING_SNAKE_CASE							(			self      :	str)						->Dict:





           '''simple docstring'''

           pass


    @unittest.skip(reason='''EfficientFormer does not support input and output embeddings''')
    def        SCREAMING_SNAKE_CASE							(			self      :	str)						->int:





           '''simple docstring'''

           pass


    def        SCREAMING_SNAKE_CASE							(			self      :	Optional[int])						->Tuple:





           '''simple docstring'''

           A__       =    self.model_tester.prepare_config_and_inputs_for_common()

           for model_class in self.all_model_classes:
                  A__       =    model_class(_SCREAMING_SNAKE_CASE)
                  A__       =    inspect.signature(model.call)
                  # signature.parameters is an OrderedDict => so arg_names order is deterministic
                  A__       =    [*signature.parameters.keys()]

                  A__       =    ["""pixel_values"""]
                  self.assertListEqual(arg_names[:1]					, _SCREAMING_SNAKE_CASE)


    def        SCREAMING_SNAKE_CASE							(			self      :	int)						->List[Any]:





           '''simple docstring'''

           def check_hidden_states_output(UpperCAmelCase__      :	Tuple					, UpperCAmelCase__      :	Optional[int]					, UpperCAmelCase__      :	str):
                  A__       =    model_class(_SCREAMING_SNAKE_CASE)

                  A__       =    model(**self._prepare_for_class(_SCREAMING_SNAKE_CASE					, _SCREAMING_SNAKE_CASE)					, training=_SCREAMING_SNAKE_CASE)
                  A__       =    outputs.encoder_hidden_states if config.is_encoder_decoder else outputs.hidden_states

                  A__       =    getattr(
                      self.model_tester					, '''expected_num_hidden_layers'''					, self.model_tester.num_hidden_layers + 1)
                  self.assertEqual(len(_SCREAMING_SNAKE_CASE)					, _SCREAMING_SNAKE_CASE)

                  if hasattr(self.model_tester					, '''encoder_seq_length'''):
                         A__       =    self.model_tester.encoder_seq_length
                         if hasattr(self.model_tester					, '''chunk_length''') and self.model_tester.chunk_length > 1:
                                A__       =    seq_length * self.model_tester.chunk_length
                  else:
                         A__       =    self.model_tester.seq_length

                  self.assertListEqual(
                      list(hidden_states[-1].shape[-2:])					, [seq_length, self.model_tester.hidden_size]					, )

                  if config.is_encoder_decoder:
                         A__       =    outputs.decoder_hidden_states

                         self.asseretIsInstance(_SCREAMING_SNAKE_CASE					, (list, tuple))
                         self.assertEqual(len(_SCREAMING_SNAKE_CASE)					, _SCREAMING_SNAKE_CASE)
                         A__       =    getattr(self.model_tester					, '''seq_length'''					, _SCREAMING_SNAKE_CASE)
                         A__       =    getattr(self.model_tester					, '''decoder_seq_length'''					, _SCREAMING_SNAKE_CASE)

                         self.assertListEqual(
                             list(hidden_states[-1].shape[-2:])					, [decoder_seq_length, self.model_tester.hidden_size]					, )

           A__       =    self.model_tester.prepare_config_and_inputs_for_common()

           for model_class in self.all_model_classes:
                  A__       =    True
                  check_hidden_states_output(_SCREAMING_SNAKE_CASE					, _SCREAMING_SNAKE_CASE					, _SCREAMING_SNAKE_CASE)

                  # check that output_hidden_states also work using config
                  del inputs_dict["output_hidden_states"]
                  A__       =    True

                  check_hidden_states_output(_SCREAMING_SNAKE_CASE					, _SCREAMING_SNAKE_CASE					, _SCREAMING_SNAKE_CASE)


    def        SCREAMING_SNAKE_CASE							(			self      :	int					, UpperCAmelCase__      :	Union[str, Any]					, UpperCAmelCase__      :	Any					, UpperCAmelCase__      :	int=False)						->Dict:





           '''simple docstring'''

           A__       =    super()._prepare_for_class(_SCREAMING_SNAKE_CASE					, _SCREAMING_SNAKE_CASE					, return_labels=_SCREAMING_SNAKE_CASE)

           if return_labels:
                  if model_class.__name__ == "TFEfficientFormerForImageClassificationWithTeacher":
                         del inputs_dict["labels"]

           return inputs_dict


    def        SCREAMING_SNAKE_CASE							(			self      :	List[str])						->int:





           '''simple docstring'''

           A__       =    self.model_tester.prepare_config_and_inputs()
           self.model_tester.create_and_check_model(*_SCREAMING_SNAKE_CASE)


    @unittest.skip(reason='''EfficientFormer does not implement masked image modeling yet''')
    def        SCREAMING_SNAKE_CASE							(			self      :	Union[str, Any])						->List[Any]:





           '''simple docstring'''

           A__       =    self.model_tester.prepare_config_and_inputs()
           self.model_tester.create_and_check_for_masked_image_modeling(*_SCREAMING_SNAKE_CASE)


    def        SCREAMING_SNAKE_CASE							(			self      :	List[str])						->int:





           '''simple docstring'''

           A__       =    self.model_tester.prepare_config_and_inputs()
           self.model_tester.create_and_check_for_image_classification(*_SCREAMING_SNAKE_CASE)


    @slow
    def        SCREAMING_SNAKE_CASE							(			self      :	Any)						->int:





           '''simple docstring'''

           for model_name in TF_EFFICIENTFORMER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
                  A__       =    TFEfficientFormerModel.from_pretrained(_SCREAMING_SNAKE_CASE)
                  self.assertIsNotNone(_SCREAMING_SNAKE_CASE)


    def        SCREAMING_SNAKE_CASE							(			self      :	str)						->List[Any]:





           '''simple docstring'''

           A__       =    self.model_tester.prepare_config_and_inputs_for_common()
           A__       =    True

           A__       =    getattr(self.model_tester					, '''seq_length'''					, _SCREAMING_SNAKE_CASE)
           A__       =    getattr(self.model_tester					, '''encoder_seq_length'''					, _SCREAMING_SNAKE_CASE)
           A__       =    getattr(self.model_tester					, '''key_length'''					, _SCREAMING_SNAKE_CASE)
           A__       =    getattr(self.model_tester					, '''chunk_length'''					, _SCREAMING_SNAKE_CASE)

           if chunk_length is not None and hasattr(self.model_tester					, '''num_hashes'''):
                  A__       =    encoder_seq_length * self.model_tester.num_hashes

           for model_class in self.all_model_classes:
                  A__       =    True
                  A__       =    False
                  A__       =    True
                  A__       =    model_class(_SCREAMING_SNAKE_CASE)

                  A__       =    model(**self._prepare_for_class(_SCREAMING_SNAKE_CASE					, _SCREAMING_SNAKE_CASE)					, training=_SCREAMING_SNAKE_CASE)
                  A__       =    outputs.encoder_attentions if config.is_encoder_decoder else outputs.attentions
                  self.assertEqual(len(_SCREAMING_SNAKE_CASE)					, self.model_tester.num_attention_outputs)

                  # check that output_attentions also work using config
                  del inputs_dict["output_attentions"]
                  A__       =    True
                  A__       =    model_class(_SCREAMING_SNAKE_CASE)
                  A__       =    model(**self._prepare_for_class(_SCREAMING_SNAKE_CASE					, _SCREAMING_SNAKE_CASE)					, training=_SCREAMING_SNAKE_CASE)

                  A__       =    outputs.encoder_attentions if config.is_encoder_decoder else outputs.attentions
                  self.assertEqual(len(_SCREAMING_SNAKE_CASE)					, self.model_tester.num_attention_outputs)

                  if chunk_length is not None:
                         self.assertListEqual(
                             list(attentions[0].shape[-4:])					, [self.model_tester.num_attention_heads, encoder_seq_length, chunk_length, encoder_key_length]					, )
                  else:
                         self.assertListEqual(
                             list(attentions[0].shape[-3:])					, [self.model_tester.num_attention_heads, encoder_seq_length, encoder_key_length]					, )





    def        SCREAMING_SNAKE_CASE							(			self      :	Any)						->int:





           '''simple docstring'''

           A__       =    self.model_tester.prepare_config_and_inputs_for_common()

           for model_class in self.all_model_classes:
                  # Prepare our model
                  A__       =    model_class(_SCREAMING_SNAKE_CASE)
                  # These are maximally general inputs for the model, with multiple None dimensions
                  # Hopefully this will catch any conditionals that fail for flexible shapes
                  A__       =    {
                      key: tf.keras.Input(shape=val.shape[1:]					, dtype=val.dtype					, name=_SCREAMING_SNAKE_CASE)
                      for key, val in model.input_signature.items()
                      if key in model.dummy_inputs
                  }
                  A__       =    model(_SCREAMING_SNAKE_CASE)
                  self.assertTrue(outputs_dict is not None)







def SCREAMING_SNAKE_CASE				(       )   ->       Any:



       """simple docstring"""

       A__       =    Image.open('''./tests/fixtures/tests_samples/COCO/000000039769.png'''						)
       return image


@require_tf
@require_vision
class 				UpperCamelCase_    ( unittest.TestCase     ):

    '''simple docstring'''






    @cached_property
    def        SCREAMING_SNAKE_CASE							(			self      :	Dict)						->List[str]:





           '''simple docstring'''

           return (
               EfficientFormerImageProcessor.from_pretrained('''snap-research/efficientformer-l1-300''')
               if is_vision_available()
               else None
           )


    @slow
    def        SCREAMING_SNAKE_CASE							(			self      :	Union[str, Any])						->Any:





           '''simple docstring'''

           A__       =    TFEfficientFormerForImageClassification.from_pretrained('''snap-research/efficientformer-l1-300''')
           A__       =    self.default_image_processor
           A__       =    prepare_img()
           A__       =    image_processor(images=_SCREAMING_SNAKE_CASE					, return_tensors='''tf''')
           # forward pass
           A__       =    model(**_SCREAMING_SNAKE_CASE					, training=_SCREAMING_SNAKE_CASE)
           # verify the logits
           A__       =    tf.TensorShape((1, 1_000))
           self.assertEqual(outputs.logits.shape					, _SCREAMING_SNAKE_CASE)
           A__       =    tf.constant([-0.0555, 0.4825, -0.0852])
           self.assertTrue(np.allclose(outputs.logits[0, :3]					, _SCREAMING_SNAKE_CASE					, atol=1e-4))





    @slow
    def        SCREAMING_SNAKE_CASE							(			self      :	Dict)						->str:





           '''simple docstring'''

           A__       =    TFEfficientFormerForImageClassificationWithTeacher.from_pretrained(
               '''snap-research/efficientformer-l1-300''')
           A__       =    self.default_image_processor
           A__       =    prepare_img()
           A__       =    image_processor(images=_SCREAMING_SNAKE_CASE					, return_tensors='''tf''')
           # forward pass
           A__       =    model(**_SCREAMING_SNAKE_CASE					, training=_SCREAMING_SNAKE_CASE)
           # verify the logits
           A__       =    tf.TensorShape((1, 1_000))
           self.assertEqual(outputs.logits.shape					, _SCREAMING_SNAKE_CASE)
           A__       =    tf.constant([-0.1312, 0.4353, -1.0499])
           self.assertTrue(np.allclose(outputs.logits[0, :3]					, _SCREAMING_SNAKE_CASE					, atol=1e-4))







"""simple docstring"""
A:   int								=		range(2, 2_0 + 1)
A:   Any								=		[1_0**k for k in range(ks[-1] + 1)]
A:   dict[int, dict[int, list[list[int]]]]								=		{}

def       _snake_case						(						UpperCamelCase						:		Dict			,		UpperCamelCase						:		Any			,		UpperCamelCase						:		Any			,		UpperCamelCase						:		int						):
 UpperCAmelCase	:					List[str]	=	sum(a_i[j] for j in range(UpperCamelCase			,		len(UpperCamelCase						)						)						)
 UpperCAmelCase	:					str	=	sum(a_i[j] * base[j] for j in range(min(len(UpperCamelCase						)			,		UpperCamelCase						)						)						)

 UpperCAmelCase	,		UpperCAmelCase	:					str	=	0, 0
 UpperCAmelCase	:					Optional[Any]	=	n - i

 UpperCAmelCase	:					Optional[int]	=	memo.get(UpperCamelCase						)

 if sub_memo is not None:
  UpperCAmelCase	:					str	=	sub_memo.get(UpperCamelCase						)

  if jumps is not None and len(UpperCamelCase						) > 0:
   # find and make the largest jump without going over
   UpperCAmelCase	:					Tuple	=	-1
   for _k in range(len(UpperCamelCase						) - 1			,		-1			,		-1						):
    if jumps[_k][2] <= k and jumps[_k][1] <= max_dn:
     UpperCAmelCase	:					int	=	_k
     break

   if max_jump >= 0:
    UpperCAmelCase	,		UpperCAmelCase	,		UpperCAmelCase	:					Optional[Any]	=	jumps[max_jump]
    # since the difference between jumps is cached, add c
    UpperCAmelCase	:					List[str]	=	diff + c
    for j in range(min(UpperCamelCase			,		len(UpperCamelCase						)						)						):
     UpperCAmelCase	,		UpperCAmelCase	:					Union[str, Any]	=	divmod(UpperCamelCase			,		10						)
    if new_c > 0:
     add(UpperCamelCase			,		UpperCamelCase			,		UpperCamelCase						)

  else:
   UpperCAmelCase	:					int	=	[]
 else:
  UpperCAmelCase	:					List[str]	=	{c: []}
  UpperCAmelCase	:					str	=	sub_memo

 if dn >= max_dn or c + diff >= base[k]:
  return diff, dn

 if k > ks[0]:
  while True:
   # keep doing smaller jumps
   UpperCAmelCase	,		UpperCAmelCase	:					List[str]	=	next_term(UpperCamelCase			,		k - 1			,		i + dn			,		UpperCamelCase						)
   diff += _diff
   dn += terms_jumped

   if dn >= max_dn or c + diff >= base[k]:
    break
 else:
  # would be too small a jump, just compute sequential terms instead
  UpperCAmelCase	,		UpperCAmelCase	:					int	=	compute(UpperCamelCase			,		UpperCamelCase			,		i + dn			,		UpperCamelCase						)
  diff += _diff
  dn += terms_jumped

 UpperCAmelCase	:					Dict	=	sub_memo[c]

 # keep jumps sorted by # of terms skipped
 UpperCAmelCase	:					str	=	0
 while j < len(UpperCamelCase						):
  if jumps[j][1] > dn:
   break
  j += 1

 # cache the jump for this value digitsum(b) and c
 sub_memo[c].insert(UpperCamelCase			,		(diff, dn, k)						)
 return (diff, dn)

def       _snake_case						(						UpperCamelCase						:		int			,		UpperCamelCase						:		Tuple			,		UpperCamelCase						:		Union[str, Any]			,		UpperCamelCase						:		Any						):
 if i >= n:
  return 0, i
 if k > len(UpperCamelCase						):
  a_i.extend([0 for _ in range(k - len(UpperCamelCase						)						)]						)

 # note: a_i -> b * 10^k + c
 # ds_b -> digitsum(b)
 # ds_c -> digitsum(c)
 UpperCAmelCase	:					List[str]	=	i
 UpperCAmelCase	,		UpperCAmelCase	,		UpperCAmelCase	:					Optional[int]	=	0, 0, 0
 for j in range(len(UpperCamelCase						)						):
  if j >= k:
   ds_b += a_i[j]
  else:
   ds_c += a_i[j]

 while i < n:
  i += 1
  UpperCAmelCase	:					Optional[int]	=	ds_c + ds_b
  diff += addend
  UpperCAmelCase	:					str	=	0
  for j in range(UpperCamelCase						):
   UpperCAmelCase	:					Any	=	a_i[j] + addend
   UpperCAmelCase	,		UpperCAmelCase	:					Any	=	divmod(UpperCamelCase			,		10						)

   ds_c += a_i[j]

  if addend > 0:
   break

 if addend > 0:
  add(UpperCamelCase			,		UpperCamelCase			,		UpperCamelCase						)
 return diff, i - start_i

def       _snake_case						(						UpperCamelCase						:		Union[str, Any]			,		UpperCamelCase						:		str			,		UpperCamelCase						:		Optional[int]						):
 for j in range(UpperCamelCase			,		len(UpperCamelCase						)						):
  UpperCAmelCase	:					Optional[int]	=	digits[j] + addend
  if s >= 10:
   UpperCAmelCase	,		UpperCAmelCase	:					int	=	divmod(UpperCamelCase			,		10						)
   UpperCAmelCase	:					str	=	addend // 10 + quotient
  else:
   UpperCAmelCase	:					Any	=	s
   UpperCAmelCase	:					Union[str, Any]	=	addend // 10

  if addend == 0:
   break

 while addend > 0:
  UpperCAmelCase	,		UpperCAmelCase	:					Any	=	divmod(UpperCamelCase			,		10						)
  digits.append(UpperCamelCase						)

def       _snake_case						(						UpperCamelCase						:		int = 10**15						):
 UpperCAmelCase	:					Dict	=	[1]
 UpperCAmelCase	:					int	=	1
 UpperCAmelCase	:					Tuple	=	0
 while True:
  UpperCAmelCase	,		UpperCAmelCase	:					Tuple	=	next_term(UpperCamelCase			,		20			,		i + dn			,		UpperCamelCase						)
  dn += terms_jumped
  if dn == n - i:
   break

 UpperCAmelCase	:					Any	=	0
 for j in range(len(UpperCamelCase						)						):
  a_n += digits[j] * 10**j
 return a_n


if __name__ == "__main__":
      print(f"""{solution() = }""")
