





UpperCAmelCase_  							=				[sum(int(c, 10) ** 2 for c in i.__str__()) for i in range(10_0000)]




def 	lowerCAmelCase_					(						__UpperCAmelCase:    int   )   ->			int:
    UpperCamelCase__							:       Optional[Any]      =   0
    while number:
        # Increased Speed Slightly by checking every 5 digits together.
        sum_of_digits_squared += DIGITS_SQUARED[number % 10_0000]
        number //= 10_0000

    return sum_of_digits_squared


# There are 2 Chains made,
# One ends with 89 with the chain member 58 being the one which when declared first,
# there will be the least number of iterations for all the members to be checked.

# The other one ends with 1 and has only one element 1.

# So 58 and 1 are chosen to be declared at the starting.

# Changed dictionary to an array to quicken the solution
UpperCAmelCase_  							=				[None] * 1000_0000
UpperCAmelCase_  							=				True
UpperCAmelCase_  							=				False




def 	lowerCAmelCase_					(						__UpperCAmelCase:    int   )   ->			bool:

    if CHAINS[number - 1] is not None:
        return CHAINS[number - 1]  # type: ignore

    UpperCamelCase__							:       Union[str, Any]      =   chain(next_number(__UpperCAmelCase   )   )
    UpperCamelCase__							:       List[Any]      =   number_chain

    while number < 1000_0000:
        UpperCamelCase__							:       Tuple      =   number_chain
        number *= 10

    return number_chain




def 	lowerCAmelCase_					(						__UpperCAmelCase:    int = 1000_0000   )   ->			int:
    for i in range(1	,     __UpperCAmelCase   ):
        if CHAINS[i] is None:
            chain(i + 1   )

    return CHAINS[:number].count(__UpperCAmelCase   )


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  print(F'''{solution() = }''')








import argparse
import json
from collections import OrderedDict
from pathlib import Path

import requests
import torch
from huggingface_hub import hf_hub_download
from PIL import Image

from transformers import (
    ConditionalDetrConfig,
    ConditionalDetrForObjectDetection,
    ConditionalDetrForSegmentation,
    ConditionalDetrImageProcessor,
)
from transformers.utils import logging


logging.set_verbosity_info()
UpperCAmelCase_  							=				logging.get_logger(__name__)

# here we list all keys to be renamed (original name on the left, our name on the right)
UpperCAmelCase_  							=				[]
for i in range(6):
  # encoder layers: output projection, 2 feedforward neural networks and 2 layernorms
  rename_keys.append(
      (F'''transformer.encoder.layers.{i}.self_attn.out_proj.weight''', F'''encoder.layers.{i}.self_attn.out_proj.weight''')
  )
  rename_keys.append(
      (F'''transformer.encoder.layers.{i}.self_attn.out_proj.bias''', F'''encoder.layers.{i}.self_attn.out_proj.bias''')
  )
  rename_keys.append((F'''transformer.encoder.layers.{i}.linear1.weight''', F'''encoder.layers.{i}.fc1.weight'''))
  rename_keys.append((F'''transformer.encoder.layers.{i}.linear1.bias''', F'''encoder.layers.{i}.fc1.bias'''))
  rename_keys.append((F'''transformer.encoder.layers.{i}.linear2.weight''', F'''encoder.layers.{i}.fc2.weight'''))
  rename_keys.append((F'''transformer.encoder.layers.{i}.linear2.bias''', F'''encoder.layers.{i}.fc2.bias'''))
  rename_keys.append(
      (F'''transformer.encoder.layers.{i}.norm1.weight''', F'''encoder.layers.{i}.self_attn_layer_norm.weight''')
  )
  rename_keys.append((F'''transformer.encoder.layers.{i}.norm1.bias''', F'''encoder.layers.{i}.self_attn_layer_norm.bias'''))
  rename_keys.append((F'''transformer.encoder.layers.{i}.norm2.weight''', F'''encoder.layers.{i}.final_layer_norm.weight'''))
  rename_keys.append((F'''transformer.encoder.layers.{i}.norm2.bias''', F'''encoder.layers.{i}.final_layer_norm.bias'''))
  # decoder layers: 2 times output projection, 2 feedforward neural networks and 3 layernorms
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.self_attn.out_proj.weight''', F'''decoder.layers.{i}.self_attn.out_proj.weight''')
  )
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.self_attn.out_proj.bias''', F'''decoder.layers.{i}.self_attn.out_proj.bias''')
  )
  rename_keys.append(
      (
          F'''transformer.decoder.layers.{i}.cross_attn.out_proj.weight''',
          F'''decoder.layers.{i}.encoder_attn.out_proj.weight''',
      )
  )
  rename_keys.append(
      (
          F'''transformer.decoder.layers.{i}.cross_attn.out_proj.bias''',
          F'''decoder.layers.{i}.encoder_attn.out_proj.bias''',
      )
  )
  rename_keys.append((F'''transformer.decoder.layers.{i}.linear1.weight''', F'''decoder.layers.{i}.fc1.weight'''))
  rename_keys.append((F'''transformer.decoder.layers.{i}.linear1.bias''', F'''decoder.layers.{i}.fc1.bias'''))
  rename_keys.append((F'''transformer.decoder.layers.{i}.linear2.weight''', F'''decoder.layers.{i}.fc2.weight'''))
  rename_keys.append((F'''transformer.decoder.layers.{i}.linear2.bias''', F'''decoder.layers.{i}.fc2.bias'''))
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.norm1.weight''', F'''decoder.layers.{i}.self_attn_layer_norm.weight''')
  )
  rename_keys.append((F'''transformer.decoder.layers.{i}.norm1.bias''', F'''decoder.layers.{i}.self_attn_layer_norm.bias'''))
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.norm2.weight''', F'''decoder.layers.{i}.encoder_attn_layer_norm.weight''')
  )
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.norm2.bias''', F'''decoder.layers.{i}.encoder_attn_layer_norm.bias''')
  )
  rename_keys.append((F'''transformer.decoder.layers.{i}.norm3.weight''', F'''decoder.layers.{i}.final_layer_norm.weight'''))
  rename_keys.append((F'''transformer.decoder.layers.{i}.norm3.bias''', F'''decoder.layers.{i}.final_layer_norm.bias'''))

  # q, k, v projections in self/cross-attention in decoder for conditional DETR
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.sa_qcontent_proj.weight''', F'''decoder.layers.{i}.sa_qcontent_proj.weight''')
  )
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.sa_kcontent_proj.weight''', F'''decoder.layers.{i}.sa_kcontent_proj.weight''')
  )
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.sa_qpos_proj.weight''', F'''decoder.layers.{i}.sa_qpos_proj.weight''')
  )
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.sa_kpos_proj.weight''', F'''decoder.layers.{i}.sa_kpos_proj.weight''')
  )
  rename_keys.append((F'''transformer.decoder.layers.{i}.sa_v_proj.weight''', F'''decoder.layers.{i}.sa_v_proj.weight'''))
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.ca_qcontent_proj.weight''', F'''decoder.layers.{i}.ca_qcontent_proj.weight''')
  )
  # rename_keys.append((f"transformer.decoder.layers.{i}.ca_qpos_proj.weight", f"decoder.layers.{i}.ca_qpos_proj.weight"))
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.ca_kcontent_proj.weight''', F'''decoder.layers.{i}.ca_kcontent_proj.weight''')
  )
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.ca_kpos_proj.weight''', F'''decoder.layers.{i}.ca_kpos_proj.weight''')
  )
  rename_keys.append((F'''transformer.decoder.layers.{i}.ca_v_proj.weight''', F'''decoder.layers.{i}.ca_v_proj.weight'''))
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.ca_qpos_sine_proj.weight''', F'''decoder.layers.{i}.ca_qpos_sine_proj.weight''')
  )

  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.sa_qcontent_proj.bias''', F'''decoder.layers.{i}.sa_qcontent_proj.bias''')
  )
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.sa_kcontent_proj.bias''', F'''decoder.layers.{i}.sa_kcontent_proj.bias''')
  )
  rename_keys.append((F'''transformer.decoder.layers.{i}.sa_qpos_proj.bias''', F'''decoder.layers.{i}.sa_qpos_proj.bias'''))
  rename_keys.append((F'''transformer.decoder.layers.{i}.sa_kpos_proj.bias''', F'''decoder.layers.{i}.sa_kpos_proj.bias'''))
  rename_keys.append((F'''transformer.decoder.layers.{i}.sa_v_proj.bias''', F'''decoder.layers.{i}.sa_v_proj.bias'''))
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.ca_qcontent_proj.bias''', F'''decoder.layers.{i}.ca_qcontent_proj.bias''')
  )
  # rename_keys.append((f"transformer.decoder.layers.{i}.ca_qpos_proj.bias", f"decoder.layers.{i}.ca_qpos_proj.bias"))
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.ca_kcontent_proj.bias''', F'''decoder.layers.{i}.ca_kcontent_proj.bias''')
  )
  rename_keys.append((F'''transformer.decoder.layers.{i}.ca_kpos_proj.bias''', F'''decoder.layers.{i}.ca_kpos_proj.bias'''))
  rename_keys.append((F'''transformer.decoder.layers.{i}.ca_v_proj.bias''', F'''decoder.layers.{i}.ca_v_proj.bias'''))
  rename_keys.append(
      (F'''transformer.decoder.layers.{i}.ca_qpos_sine_proj.bias''', F'''decoder.layers.{i}.ca_qpos_sine_proj.bias''')
  )

# convolutional projection + query embeddings + layernorm of decoder + class and bounding box heads
# for conditional DETR, also convert reference point head and query scale MLP
rename_keys.extend(
    [
        ('input_proj.weight', 'input_projection.weight'),
        ('input_proj.bias', 'input_projection.bias'),
        ('query_embed.weight', 'query_position_embeddings.weight'),
        ('transformer.decoder.norm.weight', 'decoder.layernorm.weight'),
        ('transformer.decoder.norm.bias', 'decoder.layernorm.bias'),
        ('class_embed.weight', 'class_labels_classifier.weight'),
        ('class_embed.bias', 'class_labels_classifier.bias'),
        ('bbox_embed.layers.0.weight', 'bbox_predictor.layers.0.weight'),
        ('bbox_embed.layers.0.bias', 'bbox_predictor.layers.0.bias'),
        ('bbox_embed.layers.1.weight', 'bbox_predictor.layers.1.weight'),
        ('bbox_embed.layers.1.bias', 'bbox_predictor.layers.1.bias'),
        ('bbox_embed.layers.2.weight', 'bbox_predictor.layers.2.weight'),
        ('bbox_embed.layers.2.bias', 'bbox_predictor.layers.2.bias'),
        ('transformer.decoder.ref_point_head.layers.0.weight', 'decoder.ref_point_head.layers.0.weight'),
        ('transformer.decoder.ref_point_head.layers.0.bias', 'decoder.ref_point_head.layers.0.bias'),
        ('transformer.decoder.ref_point_head.layers.1.weight', 'decoder.ref_point_head.layers.1.weight'),
        ('transformer.decoder.ref_point_head.layers.1.bias', 'decoder.ref_point_head.layers.1.bias'),
        ('transformer.decoder.query_scale.layers.0.weight', 'decoder.query_scale.layers.0.weight'),
        ('transformer.decoder.query_scale.layers.0.bias', 'decoder.query_scale.layers.0.bias'),
        ('transformer.decoder.query_scale.layers.1.weight', 'decoder.query_scale.layers.1.weight'),
        ('transformer.decoder.query_scale.layers.1.bias', 'decoder.query_scale.layers.1.bias'),
        ('transformer.decoder.layers.0.ca_qpos_proj.weight', 'decoder.layers.0.ca_qpos_proj.weight'),
        ('transformer.decoder.layers.0.ca_qpos_proj.bias', 'decoder.layers.0.ca_qpos_proj.bias'),
    ]
)




def 	lowerCAmelCase_					(						__UpperCAmelCase:    Tuple	,     __UpperCAmelCase:    List[Any]	,     __UpperCAmelCase:    Dict   )   ->			Dict:
    UpperCamelCase__							:       List[str]      =   state_dict.pop(__UpperCAmelCase   )
    UpperCamelCase__							:       Union[str, Any]      =   val




def 	lowerCAmelCase_					(						__UpperCAmelCase:    Dict   )   ->			List[str]:
    UpperCamelCase__							:       List[str]      =   OrderedDict()
    for key, value in state_dict.items():
        if "backbone.0.body" in key:
            UpperCamelCase__							:       Optional[Any]      =   key.replace('''backbone.0.body'''	,     '''backbone.conv_encoder.model'''   )
            UpperCamelCase__							:       List[str]      =   value
        else:
            UpperCamelCase__							:       Optional[int]      =   value

    return new_state_dict




def 	lowerCAmelCase_					(						__UpperCAmelCase:    Optional[int]	,     __UpperCAmelCase:    Optional[int]=False   )   ->			Optional[int]:
    UpperCamelCase__							:       List[str]      =   ''''''
    if is_panoptic:
        UpperCamelCase__							:       List[Any]      =   '''conditional_detr.'''

    # first: transformer encoder
    for i in range(6   ):
        # read in weights + bias of input projection layer (in PyTorch's MultiHeadAttention, this is a single matrix + bias)
        UpperCamelCase__							:       List[Any]      =   state_dict.pop(f"{prefix}transformer.encoder.layers.{i}.self_attn.in_proj_weight"   )
        UpperCamelCase__							:       int      =   state_dict.pop(f"{prefix}transformer.encoder.layers.{i}.self_attn.in_proj_bias"   )
        # next, add query, keys and values (in that order) to the state dict
        UpperCamelCase__							:       Any      =   in_proj_weight[:256, :]
        UpperCamelCase__							:       List[str]      =   in_proj_bias[:256]
        UpperCamelCase__							:       Optional[int]      =   in_proj_weight[256:512, :]
        UpperCamelCase__							:       List[str]      =   in_proj_bias[256:512]
        UpperCamelCase__							:       Tuple      =   in_proj_weight[-256:, :]
        UpperCamelCase__							:       List[Any]      =   in_proj_bias[-256:]




def 	lowerCAmelCase_					(						)   ->			int:
    UpperCamelCase__							:       Any      =   '''http://images.cocodataset.org/val2017/000000039769.jpg'''
    UpperCamelCase__							:       Optional[int]      =   Image.open(requests.get(__UpperCAmelCase	,     stream=__UpperCAmelCase   ).raw   )

    return im




@torch.no_grad()
def 	lowerCAmelCase_					(						__UpperCAmelCase:    Any	,     __UpperCAmelCase:    Any   )   ->			Optional[int]:
    UpperCamelCase__							:       Tuple      =   ConditionalDetrConfig()
    # set backbone and dilation attributes
    if "resnet101" in model_name:
        UpperCamelCase__							:       Optional[Any]      =   '''resnet101'''
    if "dc5" in model_name:
        UpperCamelCase__							:       Dict      =   True
    UpperCamelCase__							:       Union[str, Any]      =   '''panoptic''' in model_name
    if is_panoptic:
        UpperCamelCase__							:       Any      =   250
    else:
        UpperCamelCase__							:       int      =   91
        UpperCamelCase__							:       List[str]      =   '''huggingface/label-files'''
        UpperCamelCase__							:       List[str]      =   '''coco-detection-id2label.json'''
        UpperCamelCase__							:       Tuple      =   json.load(open(hf_hub_download(__UpperCAmelCase	,     __UpperCAmelCase	,     repo_type='''dataset'''   )	,     '''r'''   )   )
        UpperCamelCase__							:       List[str]      =   {int(__UpperCAmelCase   ): v for k, v in idalabel.items()}
        UpperCamelCase__							:       Dict      =   idalabel
        UpperCamelCase__							:       Dict      =   {v: k for k, v in idalabel.items()}

    # load image processor
    UpperCamelCase__							:       int      =   '''coco_panoptic''' if is_panoptic else '''coco_detection'''
    UpperCamelCase__							:       str      =   ConditionalDetrImageProcessor(format=__UpperCAmelCase   )

    # prepare image
    UpperCamelCase__							:       Tuple      =   prepare_img()
    UpperCamelCase__							:       List[str]      =   image_processor(images=__UpperCAmelCase	,     return_tensors='''pt'''   )
    UpperCamelCase__							:       Union[str, Any]      =   encoding['''pixel_values''']

    logger.info(f"Converting model {model_name}..."   )

    # load original model from torch hub
    UpperCamelCase__							:       Union[str, Any]      =   torch.hub.load('''DeppMeng/ConditionalDETR'''	,     __UpperCAmelCase	,     pretrained=__UpperCAmelCase   ).eval()
    UpperCamelCase__							:       Optional[int]      =   conditional_detr.state_dict()
    # rename keys
    for src, dest in rename_keys:
        if is_panoptic:
            UpperCamelCase__							:       List[str]      =   '''conditional_detr.''' + src
        rename_key(__UpperCAmelCase	,     __UpperCAmelCase	,     __UpperCAmelCase   )
    UpperCamelCase__							:       str      =   rename_backbone_keys(__UpperCAmelCase   )
    # query, key and value matrices need special treatment
    read_in_q_k_v(__UpperCAmelCase	,     is_panoptic=__UpperCAmelCase   )
    # important: we need to prepend a prefix to each of the base model keys as the head models use different attributes for them
    UpperCamelCase__							:       List[str]      =   '''conditional_detr.model.''' if is_panoptic else '''model.'''
    for key in state_dict.copy().keys():
        if is_panoptic:
            if (
                key.startswith('''conditional_detr'''   )
                and not key.startswith('''class_labels_classifier'''   )
                and not key.startswith('''bbox_predictor'''   )
            ):
                UpperCamelCase__							:       Tuple      =   state_dict.pop(__UpperCAmelCase   )
                UpperCamelCase__							:       List[Any]      =   val
            elif "class_labels_classifier" in key or "bbox_predictor" in key:
                UpperCamelCase__							:       Any      =   state_dict.pop(__UpperCAmelCase   )
                UpperCamelCase__							:       Dict      =   val
            elif key.startswith('''bbox_attention'''   ) or key.startswith('''mask_head'''   ):
                continue
            else:
                UpperCamelCase__							:       List[Any]      =   state_dict.pop(__UpperCAmelCase   )
                UpperCamelCase__							:       Optional[int]      =   val
        else:
            if not key.startswith('''class_labels_classifier'''   ) and not key.startswith('''bbox_predictor'''   ):
                UpperCamelCase__							:       List[str]      =   state_dict.pop(__UpperCAmelCase   )
                UpperCamelCase__							:       Optional[int]      =   val
    # finally, create HuggingFace model and load state dict
    UpperCamelCase__							:       str      =   ConditionalDetrForSegmentation(__UpperCAmelCase   ) if is_panoptic else ConditionalDetrForObjectDetection(__UpperCAmelCase   )
    model.load_state_dict(__UpperCAmelCase   )
    model.eval()
    model.push_to_hub(repo_id=__UpperCAmelCase	,     organization='''DepuMeng'''	,     commit_message='''Add model'''   )
    # verify our conversion
    UpperCamelCase__							:       str      =   conditional_detr(__UpperCAmelCase   )
    UpperCamelCase__							:       Optional[Any]      =   model(__UpperCAmelCase   )
    assert torch.allclose(outputs.logits	,     original_outputs['''pred_logits''']	,     atol=1e-4   )
    assert torch.allclose(outputs.pred_boxes	,     original_outputs['''pred_boxes''']	,     atol=1e-4   )
    if is_panoptic:
        assert torch.allclose(outputs.pred_masks	,     original_outputs['''pred_masks''']	,     atol=1e-4   )

    # Save model and image processor
    logger.info(f"Saving PyTorch model and image processor to {pytorch_dump_folder_path}..."   )
    Path(__UpperCAmelCase   ).mkdir(exist_ok=__UpperCAmelCase   )
    model.save_pretrained(__UpperCAmelCase   )
    image_processor.save_pretrained(__UpperCAmelCase   )


if __name__ == "__main__":
  UpperCAmelCase_  							=				argparse.ArgumentParser()

  parser.add_argument(
      '--model_name',
      default='conditional_detr_resnet50',
      type=str,
      help='Name of the CONDITIONAL_DETR model you\'d like to convert.',
  )
  parser.add_argument(
      '--pytorch_dump_folder_path', default=None, type=str, help='Path to the folder to output PyTorch model.'
  )
  UpperCAmelCase_  							=				parser.parse_args()
  convert_conditional_detr_checkpoint(args.model_name, args.pytorch_dump_folder_path)

