SCREAMING_SNAKE_CASE :	Tuple							     =		range(2, 20 + 1)
SCREAMING_SNAKE_CASE :	Union[str, Any]							     =		[10**k for k in range(ks[-1] + 1)]
SCREAMING_SNAKE_CASE :	dict[int, dict[int, list[list[int]]]]							     =		{}



def   __A		(			_A							,				_A							,				_A							,				_A					):



 """simple docstring"""


 __a       =  sum(a_i[j] for j in range(_A							,				len(_A					)					)					)
 __a       =  sum(a_i[j] * base[j] for j in range(min(len(_A					)							,				_A					)					)					)

 __a       ,     __a       =  0, 0
 __a       =  n - i

 __a       =  memo.get(_A					)

 if sub_memo is not None:
  __a       =  sub_memo.get(_A					)

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

   if max_jump >= 0:
    __a       ,     __a       ,     __a       =  jumps[max_jump]
    # since the difference between jumps is cached, add c
    __a       =  diff + c
    for j in range(min(_A							,				len(_A					)					)					):
     __a       ,     __a       =  divmod(_A							,				10					)
    if new_c > 0:
     add(_A							,				_A							,				_A					)

  else:
   __a       =  []
 else:
  __a       =  {c: []}
  __a       =  sub_memo

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

 if k > ks[0]:
  while True:
   # keep doing smaller jumps
   __a       ,     __a       =  next_term(_A							,				k - 1							,				i + dn							,				_A					)
   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
  __a       ,     __a       =  compute(_A							,				_A							,				i + dn							,				_A					)
  diff += _diff
  dn += terms_jumped

 __a       =  sub_memo[c]

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

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



def   __A		(			_A							,				_A							,				_A							,				_A					):



 """simple docstring"""


 if i >= n:
  return 0, i
 if k > len(_A					):
  a_i.extend([0 for _ in range(k - len(_A					)					)]					)

 # note: a_i -> b * 10^k + c
 # ds_b -> digitsum(b)
 # ds_c -> digitsum(c)
 __a       =  i
 __a       ,     __a       ,     __a       =  0, 0, 0
 for j in range(len(_A					)					):
  if j >= k:
   ds_b += a_i[j]
  else:
   ds_c += a_i[j]

 while i < n:
  i += 1
  __a       =  ds_c + ds_b
  diff += addend
  __a       =  0
  for j in range(_A					):
   __a       =  a_i[j] + addend
   __a       ,     __a       =  divmod(_A							,				10					)

   ds_c += a_i[j]

  if addend > 0:
   break

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



def   __A		(			_A							,				_A							,				_A					):



 """simple docstring"""


 for j in range(_A							,				len(_A					)					):
  __a       =  digits[j] + addend
  if s >= 10:
   __a       ,     __a       =  divmod(_A							,				10					)
   __a       =  addend // 10 + quotient
  else:
   __a       =  s
   __a       =  addend // 10

  if addend == 0:
   break

 while addend > 0:
  __a       ,     __a       =  divmod(_A							,				10					)
  digits.append(_A					)



def   __A		(			_A = 10**15					):



 """simple docstring"""


 __a       =  [1]
 __a       =  1
 __a       =  0
 while True:
  __a       ,     __a       =  next_term(_A							,				20							,				i + dn							,				_A					)
  dn += terms_jumped
  if dn == n - i:
   break

 __a       =  0
 for j in range(len(_A					)					):
  a_n += digits[j] * 10**j
 return a_n


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



import inspect
import unittest

from transformers import ViTConfig
from transformers.testing_utils import (
    require_accelerate,
    require_torch,
    require_torch_gpu,
    require_vision,
    slow,
    torch_device,
)
from transformers.utils import cached_property, is_torch_available, is_vision_available

from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor, ids_tensor
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
  import torch
  from torch import nn

  from transformers import ViTForImageClassification, ViTForMaskedImageModeling, ViTModel
  from transformers.models.vit.modeling_vit import VIT_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
  from PIL import Image

  from transformers import ViTImageProcessor
class    A_ :

  def __init__(		self :      Union[str, Any]     ,							__SCREAMING_SNAKE_CASE :      Optional[int]     ,							__SCREAMING_SNAKE_CASE :      List[Any]=13     ,							__SCREAMING_SNAKE_CASE :      Optional[Any]=30     ,							__SCREAMING_SNAKE_CASE :      Optional[Any]=2     ,							__SCREAMING_SNAKE_CASE :      Optional[int]=3     ,							__SCREAMING_SNAKE_CASE :      List[Any]=True     ,							__SCREAMING_SNAKE_CASE :      Dict=True     ,							__SCREAMING_SNAKE_CASE :      Optional[int]=32     ,							__SCREAMING_SNAKE_CASE :      str=5     ,							__SCREAMING_SNAKE_CASE :      List[str]=4     ,							__SCREAMING_SNAKE_CASE :      List[Any]=37     ,							__SCREAMING_SNAKE_CASE :      int="gelu"     ,							__SCREAMING_SNAKE_CASE :      List[Any]=0.1     ,							__SCREAMING_SNAKE_CASE :      Optional[Any]=0.1     ,							__SCREAMING_SNAKE_CASE :      List[Any]=10     ,							__SCREAMING_SNAKE_CASE :      int=0.02     ,							__SCREAMING_SNAKE_CASE :      Dict=None     ,							__SCREAMING_SNAKE_CASE :      str=2     ,							):
   __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       =  scope
   __a       =  encoder_stride

   # in ViT, the seq length equals the number of patches + 1 (we add 1 for the [CLS] token)
   __a       =  (image_size // patch_size) ** 2
   __a       =  num_patches + 1

  def 		_UpperCAmelCase   (		self :      Any       ):
   __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 		_UpperCAmelCase   (		self :      str       ):
   return ViTConfig(
       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     ,							)

  def 		_UpperCAmelCase   (		self :      Dict     ,							__SCREAMING_SNAKE_CASE :      List[Any]     ,							__SCREAMING_SNAKE_CASE :      Dict     ,							__SCREAMING_SNAKE_CASE :      Any       ):
   __a       =  ViTModel(config=__SCREAMING_SNAKE_CASE       )
   model.to(__SCREAMING_SNAKE_CASE       )
   model.eval()
   __a       =  model(__SCREAMING_SNAKE_CASE       )
   self.parent.assertEqual(result.last_hidden_state.shape     ,							(self.batch_size, self.seq_length, self.hidden_size)       )

  def 		_UpperCAmelCase   (		self :      Union[str, Any]     ,							__SCREAMING_SNAKE_CASE :      Tuple     ,							__SCREAMING_SNAKE_CASE :      str     ,							__SCREAMING_SNAKE_CASE :      Dict       ):
   __a       =  ViTForMaskedImageModeling(config=__SCREAMING_SNAKE_CASE       )
   model.to(__SCREAMING_SNAKE_CASE       )
   model.eval()
   __a       =  model(__SCREAMING_SNAKE_CASE       )
   self.parent.assertEqual(
       result.reconstruction.shape     ,							(self.batch_size, self.num_channels, self.image_size, self.image_size)       )

   # test greyscale images
   __a       =  1
   __a       =  ViTForMaskedImageModeling(__SCREAMING_SNAKE_CASE       )
   model.to(__SCREAMING_SNAKE_CASE       )
   model.eval()

   __a       =  floats_tensor([self.batch_size, 1, self.image_size, self.image_size]       )
   __a       =  model(__SCREAMING_SNAKE_CASE       )
   self.parent.assertEqual(result.reconstruction.shape     ,							(self.batch_size, 1, self.image_size, self.image_size)       )

  def 		_UpperCAmelCase   (		self :      Optional[Any]     ,							__SCREAMING_SNAKE_CASE :      Tuple     ,							__SCREAMING_SNAKE_CASE :      Union[str, Any]     ,							__SCREAMING_SNAKE_CASE :      List[str]       ):
   __a       =  self.type_sequence_label_size
   __a       =  ViTForImageClassification(__SCREAMING_SNAKE_CASE       )
   model.to(__SCREAMING_SNAKE_CASE       )
   model.eval()
   __a       =  model(__SCREAMING_SNAKE_CASE     ,							labels=__SCREAMING_SNAKE_CASE       )
   self.parent.assertEqual(result.logits.shape     ,							(self.batch_size, self.type_sequence_label_size)       )

   # test greyscale images
   __a       =  1
   __a       =  ViTForImageClassification(__SCREAMING_SNAKE_CASE       )
   model.to(__SCREAMING_SNAKE_CASE       )
   model.eval()

   __a       =  floats_tensor([self.batch_size, 1, self.image_size, self.image_size]       )
   __a       =  model(__SCREAMING_SNAKE_CASE       )
   self.parent.assertEqual(result.logits.shape     ,							(self.batch_size, self.type_sequence_label_size)       )

  def 		_UpperCAmelCase   (		self :      List[Any]       ):
   __a       =  self.prepare_config_and_inputs()
   (
       (
       __a
   )       ,     (
       __a
   )       ,     (
       __a
   )       ,     
   )       =  config_and_inputs
   __a       =  {"pixel_values": pixel_values}
   return config, inputs_dict
@require_torch
class    A_ (       a_			,       a_			,       unittest.TestCase ):
  _SCREAMING_SNAKE_CASE    				=			(
      (
          ViTModel,
          ViTForImageClassification,
          ViTForMaskedImageModeling,
      )
      if is_torch_available()
      else ()
  )
  _SCREAMING_SNAKE_CASE    				=			(
      {"""feature-extraction""": ViTModel, """image-classification""": ViTForImageClassification}
      if is_torch_available()
      else {}
  )
  _SCREAMING_SNAKE_CASE    				=			True

  _SCREAMING_SNAKE_CASE    				=			False
  _SCREAMING_SNAKE_CASE    				=			False
  _SCREAMING_SNAKE_CASE    				=			False

  def 		_UpperCAmelCase   (		self :      Optional[Any]       ):
   __a       =  ViTModelTester(self       )
   __a       =  ConfigTester(self     ,							config_class=__SCREAMING_SNAKE_CASE     ,							has_text_modality=__SCREAMING_SNAKE_CASE     ,							hidden_size=37       )

  def 		_UpperCAmelCase   (		self :      List[str]       ):
   self.config_tester.run_common_tests()

  @unittest.skip(reason="ViT does not use inputs_embeds"       )
  def 		_UpperCAmelCase   (		self :      Optional[Any]       ):
   pass

  def 		_UpperCAmelCase   (		self :      int       ):
   __a       ,     __a       =  self.model_tester.prepare_config_and_inputs_for_common()

   for model_class in self.all_model_classes:
    __a       =  model_class(__SCREAMING_SNAKE_CASE       )
    self.assertIsInstance(model.get_input_embeddings()     ,							(nn.Module)       )
    __a       =  model.get_output_embeddings()
    self.assertTrue(x is None or isinstance(__SCREAMING_SNAKE_CASE     ,							nn.Linear       )       )

  def 		_UpperCAmelCase   (		self :      Optional[int]       ):
   __a       ,     __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.forward       )
    # 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 		_UpperCAmelCase   (		self :      List[str]       ):
   __a       =  self.model_tester.prepare_config_and_inputs()
   self.model_tester.create_and_check_model(*__SCREAMING_SNAKE_CASE       )

  def 		_UpperCAmelCase   (		self :      Any       ):
   __a       =  self.model_tester.prepare_config_and_inputs()
   self.model_tester.create_and_check_for_masked_image_modeling(*__SCREAMING_SNAKE_CASE       )

  def 		_UpperCAmelCase   (		self :      Tuple       ):
   __a       =  self.model_tester.prepare_config_and_inputs()
   self.model_tester.create_and_check_for_image_classification(*__SCREAMING_SNAKE_CASE       )

  @slow
  def 		_UpperCAmelCase   (		self :      Dict       ):
   for model_name in VIT_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
    __a       =  ViTModel.from_pretrained(__SCREAMING_SNAKE_CASE       )
    self.assertIsNotNone(__SCREAMING_SNAKE_CASE       )



def   __A		(			):



 """simple docstring"""


 __a       =  Image.open("./tests/fixtures/tests_samples/COCO/000000039769.png"					)
 return image






@require_torch
@require_vision
class    A_ (       unittest.TestCase ):

  @cached_property
  def 		_UpperCAmelCase   (		self :      List[str]       ):
   return ViTImageProcessor.from_pretrained("google/vit-base-patch16-224"       ) if is_vision_available() else None

  @slow
  def 		_UpperCAmelCase   (		self :      str       ):
   __a       =  ViTForImageClassification.from_pretrained("google/vit-base-patch16-224"       ).to(__SCREAMING_SNAKE_CASE       )

   __a       =  self.default_image_processor
   __a       =  prepare_img()
   __a       =  image_processor(images=__SCREAMING_SNAKE_CASE     ,							return_tensors="pt"       ).to(__SCREAMING_SNAKE_CASE       )

   # forward pass
   with torch.no_grad():
    __a       =  model(**__SCREAMING_SNAKE_CASE       )

   # verify the logits
   __a       =  torch.Size((1, 10_00)       )
   self.assertEqual(outputs.logits.shape     ,							__SCREAMING_SNAKE_CASE       )

   __a       =  torch.tensor([-0.27_44, 0.82_15, -0.08_36]       ).to(__SCREAMING_SNAKE_CASE       )

   self.assertTrue(torch.allclose(outputs.logits[0, :3]     ,							__SCREAMING_SNAKE_CASE     ,							atol=1E-4       )       )

  @slow
  def 		_UpperCAmelCase   (		self :      Union[str, Any]       ):
   # ViT models have an `interpolate_pos_encoding` argument in their forward method,
   # allowing to interpolate the pre-trained position embeddings in order to use
   # the model on higher resolutions. The DINO model by Facebook AI leverages this
   # to visualize self-attention on higher resolution images.
   __a       =  ViTModel.from_pretrained("facebook/dino-vits8"       ).to(__SCREAMING_SNAKE_CASE       )

   __a       =  ViTImageProcessor.from_pretrained("facebook/dino-vits8"     ,							size=4_80       )
   __a       =  prepare_img()
   __a       =  image_processor(images=__SCREAMING_SNAKE_CASE     ,							return_tensors="pt"       )
   __a       =  inputs.pixel_values.to(__SCREAMING_SNAKE_CASE       )

   # forward pass
   with torch.no_grad():
    __a       =  model(__SCREAMING_SNAKE_CASE     ,							interpolate_pos_encoding=__SCREAMING_SNAKE_CASE       )

   # verify the logits
   __a       =  torch.Size((1, 36_01, 3_84)       )
   self.assertEqual(outputs.last_hidden_state.shape     ,							__SCREAMING_SNAKE_CASE       )

   __a       =  torch.tensor(
       [[4.23_40, 4.39_06, -6.66_92], [4.54_63, 1.89_28, -6.72_57], [4.44_29, 0.84_96, -5.85_85]]       ).to(__SCREAMING_SNAKE_CASE       )

   self.assertTrue(torch.allclose(outputs.last_hidden_state[0, :3, :3]     ,							__SCREAMING_SNAKE_CASE     ,							atol=1E-4       )       )

  @slow
  @require_accelerate
  @require_torch_gpu
  def 		_UpperCAmelCase   (		self :      Any       ):
   __a       =  ViTModel.from_pretrained("facebook/dino-vits8"     ,							torch_dtype=torch.floataa     ,							device_map="auto"       )
   __a       =  self.default_image_processor

   __a       =  prepare_img()
   __a       =  image_processor(images=__SCREAMING_SNAKE_CASE     ,							return_tensors="pt"       )
   __a       =  inputs.pixel_values.to(__SCREAMING_SNAKE_CASE       )

   # forward pass to make sure inference works in fp16
   with torch.no_grad():
    __a       =  model(__SCREAMING_SNAKE_CASE       )


