


import math






def   _lowercase(					__a				:						int     ):
							a__      =[True] * n
							a__      =False
							a__      =False
							a__      =True

							for i in range(3    ,     int(n**0.5 + 1     )    ,     2     ):
														a__      =i * 2
														while index < n:
																					a__      =False
																					a__      =index + i

							a__      =[2]

							for i in range(3    ,     __a    ,     2     ):
														if is_prime[i]:
																					primes.append(__a     )

							return primes






def   _lowercase(					__a				:						int = 9999_6666_3333     ):
							a__      =math.floor(math.sqrt(__a     )     ) + 100
							a__      =prime_sieve(__a     )

							a__      =0
							a__      =0
							a__      =primes[prime_index]

							while (last_prime**2) <= limit:
														a__      =primes[prime_index + 1]

														a__      =last_prime**2
														a__      =next_prime**2

														# Get numbers divisible by lps(current)
														a__      =lower_bound + last_prime
														while upper_bound > current <= limit:
																					matches_sum += current
																					current += last_prime

														# Reset the upper_bound
														while (upper_bound - next_prime) > limit:
																					upper_bound -= next_prime

														# Add the numbers divisible by ups(current)
														a__      =upper_bound - next_prime
														while current > lower_bound:
																					matches_sum += current
																					current -= next_prime

														# Remove the numbers divisible by both ups and lps
														a__      =0
														while upper_bound > current <= limit:
																					if current <= lower_bound:
																												# Increment the current number
																												current += last_prime * next_prime
																												continue

																					if current > limit:
																												break

																					# Remove twice since it was added by both ups and lps
																					matches_sum -= current * 2

																					# Increment the current number
																					current += last_prime * next_prime

														# Setup for next pair
														a__      =next_prime
														prime_index += 1

							return matches_sum


if __name__ == "__main__":
	print(solution())





import copy
import inspect
import unittest

from transformers import AutoBackbone
from transformers.configuration_utils import PretrainedConfig
from transformers.testing_utils import require_timm, require_torch, torch_device
from transformers.utils.import_utils import is_torch_available

from ...test_backbone_common import BackboneTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, floats_tensor


if is_torch_available():
	import torch

	from transformers import TimmBackbone, TimmBackboneConfig

from ...test_pipeline_mixin import PipelineTesterMixin




class       lowercase_					:





				def __init__(				self       ,  lowercase_       ,  lowercase_=None       ,  lowercase_=None       ,  lowercase_=None       ,  lowercase_="resnet50"       ,  lowercase_=3       ,  lowercase_=32       ,  lowercase_=3       ,  lowercase_=True       ,  lowercase_=True       ,  )  -> Union[str, Any]:
											a__      =parent
											a__      =out_indices if out_indices is not None else [4]
											a__      =stage_names
											a__      =out_features
											a__      =backbone
											a__      =batch_size
											a__      =image_size
											a__      =num_channels
											a__      =use_pretrained_backbone
											a__      =is_training





				def 						__UpperCamelCase    (				self)  -> Optional[Any]:
											a__      =floats_tensor([self.batch_size, self.num_channels, self.image_size, self.image_size])
											a__      =self.get_config()

											return config, pixel_values





				def 						__UpperCamelCase    (				self)  -> Tuple:
											return TimmBackboneConfig(
											    image_size=self.image_size       ,  num_channels=self.num_channels       ,  out_features=self.out_features       ,  out_indices=self.out_indices       ,  stage_names=self.stage_names       ,  use_pretrained_backbone=self.use_pretrained_backbone       ,  backbone=self.backbone       ,  )





				def 						__UpperCamelCase    (				self       ,  lowercase_       ,  lowercase_)  -> str:
											a__      =TimmBackbone(config=lowercase_)
											model.to(lowercase_)
											model.eval()
											with torch.no_grad():
																		a__      =model(lowercase_)
											self.parent.assertEqual(
											    result.feature_map[-1].shape       ,  (self.batch_size, model.channels[-1], 14, 14)       ,  )





				def 						__UpperCamelCase    (				self)  -> str:
											a__      =self.prepare_config_and_inputs()
											a__    ,     a__      =config_and_inputs
											a__      ={'pixel_values': pixel_values}
											return config, inputs_dict







@require_torch
@require_timm
class       lowercase_					(lowercase__      ,					lowercase__      ,					lowercase__      ,					unittest.TestCase   ):
				snake_case	    =(TimmBackbone,) if is_torch_available() else ()
				snake_case	    ={'feature-extraction': TimmBackbone} if is_torch_available() else {}
				snake_case	    =False
				snake_case	    =False
				snake_case	    =False
				snake_case	    =False





				def 						__UpperCamelCase    (				self)  -> Optional[Any]:
											a__      =TimmBackboneModelTester(self)
											a__      =ConfigTester(self       ,  config_class=lowercase_       ,  has_text_modality=lowercase_)





				def 						__UpperCamelCase    (				self)  -> Dict:
											self.config_tester.create_and_test_config_to_json_string()
											self.config_tester.create_and_test_config_to_json_file()
											self.config_tester.create_and_test_config_from_and_save_pretrained()
											self.config_tester.create_and_test_config_with_num_labels()
											self.config_tester.check_config_can_be_init_without_params()
											self.config_tester.check_config_arguments_init()





				def 						__UpperCamelCase    (				self)  -> str:
											a__      ='resnet18'
											a__      ='microsoft/resnet-18'

											a__      =AutoBackbone.from_pretrained(lowercase_       ,  use_timm_backbone=lowercase_)
											a__      =AutoBackbone.from_pretrained(lowercase_)

											self.assertEqual(len(timm_model.out_features)       ,  len(transformers_model.out_features))
											self.assertEqual(len(timm_model.stage_names)       ,  len(transformers_model.stage_names))
											self.assertEqual(timm_model.channels       ,  transformers_model.channels)
											# Out indices are set to the last layer by default. For timm models, we don't know
											# the number of layers in advance, so we set it to (-1,), whereas for transformers
											# models, we set it to [len(stage_names) - 1] (kept for backward compatibility).
											self.assertEqual(timm_model.out_indices       ,  (-1,))
											self.assertEqual(transformers_model.out_indices       ,  [len(timm_model.stage_names) - 1])

											a__      =AutoBackbone.from_pretrained(lowercase_       ,  use_timm_backbone=lowercase_       ,  out_indices=[1, 2, 3])
											a__      =AutoBackbone.from_pretrained(lowercase_       ,  out_indices=[1, 2, 3])

											self.assertEqual(timm_model.out_indices       ,  transformers_model.out_indices)
											self.assertEqual(len(timm_model.out_features)       ,  len(transformers_model.out_features))
											self.assertEqual(timm_model.channels       ,  transformers_model.channels)





				@unittest.skip('TimmBackbone doesn\'t support feed forward chunking')
				def 						__UpperCamelCase    (				self)  -> int:
											pass





				@unittest.skip('TimmBackbone doesn\'t have num_hidden_layers attribute')
				def 						__UpperCamelCase    (				self)  -> List[str]:
											pass





				@unittest.skip('TimmBackbone initialization is managed on the timm side')
				def 						__UpperCamelCase    (				self)  -> Any:
											pass





				@unittest.skip('TimmBackbone models doesn\'t have inputs_embeds')
				def 						__UpperCamelCase    (				self)  -> Any:
											pass





				@unittest.skip('TimmBackbone models doesn\'t have inputs_embeds')
				def 						__UpperCamelCase    (				self)  -> List[str]:
											pass





				@unittest.skip('TimmBackbone model cannot be created without specifying a backbone checkpoint')
				def 						__UpperCamelCase    (				self)  -> Optional[int]:
											pass





				@unittest.skip('Only checkpoints on timm can be loaded into TimmBackbone')
				def 						__UpperCamelCase    (				self)  -> Union[str, Any]:
											pass





				@unittest.skip('model weights aren\'t tied in TimmBackbone.')
				def 						__UpperCamelCase    (				self)  -> Dict:
											pass





				@unittest.skip('model weights aren\'t tied in TimmBackbone.')
				def 						__UpperCamelCase    (				self)  -> List[Any]:
											pass





				@unittest.skip('Only checkpoints on timm can be loaded into TimmBackbone')
				def 						__UpperCamelCase    (				self)  -> List[str]:
											pass





				@unittest.skip('Only checkpoints on timm can be loaded into TimmBackbone')
				def 						__UpperCamelCase    (				self)  -> Union[str, Any]:
											pass





				@unittest.skip('TimmBackbone doesn\'t have hidden size info in its configuration.')
				def 						__UpperCamelCase    (				self)  -> int:
											pass





				@unittest.skip('TimmBackbone doesn\'t support output_attentions.')
				def 						__UpperCamelCase    (				self)  -> str:
											pass





				@unittest.skip('Safetensors is not supported by timm.')
				def 						__UpperCamelCase    (				self)  -> Optional[int]:
											pass





				@unittest.skip('Will be fixed soon by reducing the size of the model used for common tests.')
				def 						__UpperCamelCase    (				self)  -> Optional[Any]:
											pass





				def 						__UpperCamelCase    (				self)  -> Any:
											a__    ,     a__      =self.model_tester.prepare_config_and_inputs_for_common()

											for model_class in self.all_model_classes:
																		a__      =model_class(lowercase_)
																		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]       ,  lowercase_)





				def 						__UpperCamelCase    (				self)  -> Any:
											a__    ,     a__      =self.model_tester.prepare_config_and_inputs_for_common()
											a__      =True
											a__      =self.has_attentions

											# no need to test all models as different heads yield the same functionality
											a__      =self.all_model_classes[0]
											a__      =model_class(lowercase_)
											model.to(lowercase_)

											a__      =self._prepare_for_class(lowercase_       ,  lowercase_)
											a__      =model(**lowercase_)
											a__      =outputs[0][-1]

											# Encoder-/Decoder-only models
											a__      =outputs.hidden_states[0]
											hidden_states.retain_grad()

											if self.has_attentions:
																		a__      =outputs.attentions[0]
																		attentions.retain_grad()

											output.flatten()[0].backward(retain_graph=lowercase_)

											self.assertIsNotNone(hidden_states.grad)

											if self.has_attentions:
																		self.assertIsNotNone(attentions.grad)





				def 						__UpperCamelCase    (				self)  -> List[str]:
											a__    ,     a__      =self.model_tester.prepare_config_and_inputs_for_common()

											for model_class in self.all_model_classes:
																		a__      =model_class(lowercase_)
																		model.to(lowercase_)
																		model.eval()
																		a__      =model(**lowercase_)

																		self.assertEqual(len(result.feature_maps)       ,  len(config.out_indices))
																		self.assertEqual(len(model.channels)       ,  len(config.out_indices))

																		# Check output of last stage is taken if out_features=None, out_indices=None
																		a__      =copy.deepcopy(lowercase_)
																		a__      =None
																		a__      =model_class(lowercase_)
																		model.to(lowercase_)
																		model.eval()
																		a__      =model(**lowercase_)

																		self.assertEqual(len(result.feature_maps)       ,  1)
																		self.assertEqual(len(model.channels)       ,  1)

																		# Check backbone can be initialized with fresh weights
																		a__      =copy.deepcopy(lowercase_)
																		a__      =False
																		a__      =model_class(lowercase_)
																		model.to(lowercase_)
																		model.eval()
																		a__      =model(**lowercase_)

