


import copy
import inspect
import unittest

import numpy as np
from huggingface_hub import hf_hub_download

from transformers import TimesformerConfig
from transformers.models.auto import get_values
from transformers.testing_utils import require_torch, 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 (
						    MODEL_FOR_VIDEO_CLASSIFICATION_MAPPING,
						    TimesformerForVideoClassification,
						    TimesformerModel,
						)
						from transformers.models.timesformer.modeling_timesformer import TIMESFORMER_PRETRAINED_MODEL_ARCHIVE_LIST


if is_vision_available():
						from transformers import VideoMAEImageProcessor







class        snake_case_   :
					def __init__(      self   :Tuple			,__snake_case   :List[Any]			,__snake_case   :Optional[Any]=13			,__snake_case   :Any=10			,__snake_case   :str=3			,__snake_case   :List[Any]=2			,__snake_case   :Optional[Any]=2			,__snake_case   :Any=True			,__snake_case   :int=True			,__snake_case   :Dict=32			,__snake_case   :str=5			,__snake_case   :Tuple=4			,__snake_case   :Tuple=37			,__snake_case   :List[Any]="gelu"			,__snake_case   :Dict=0.1			,__snake_case   :Union[str, Any]=0.1			,__snake_case   :str=10			,__snake_case   :Union[str, Any]=0.02			,__snake_case   :Tuple="divided_space_time"			,__snake_case   :Optional[Any]=None			,)					->    Union[str, Any]:
												a__             =     parent
												a__             =     batch_size
												a__             =     image_size
												a__             =     num_channels
												a__             =     patch_size
												a__             =     num_frames
												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__             =     attention_type
												a__             =     initializer_range
												a__             =     scope
												a__             =     num_labels

												# in TimeSformer, the number of spatial tokens equals num_frames * num_patches per frame + 1 CLS token
												a__             =     (image_size // patch_size) ** 2
												a__             =     (num_frames) * self.num_patches_per_frame + 1
					def  lowerCamelCase__(      self   :Tuple      )					->    str:
												a__             =     floats_tensor(
												    [self.batch_size, self.num_frames, self.num_channels, self.image_size, self.image_size]      )

												a__             =     None
												if self.use_labels:
																			a__             =     ids_tensor([self.batch_size]			,self.num_labels      )

												a__             =     self.get_config()

												return config, pixel_values, labels
					def  lowerCamelCase__(      self   :Optional[int]      )					->    Optional[Any]:
												a__             =     TimesformerConfig(
												    image_size=self.image_size			,patch_size=self.patch_size			,num_channels=self.num_channels			,num_frames=self.num_frames			,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			,initializer_range=self.initializer_range			,attention_type=self.attention_type			,)
												a__             =     self.num_labels
												return config
					def  lowerCamelCase__(      self   :Optional[int]			,__snake_case   :Optional[Any]			,__snake_case   :List[str]			,__snake_case   :List[Any]      )					->    Union[str, Any]:
												a__             =     TimesformerModel(config=__snake_case      )
												model.to(__snake_case      )
												model.eval()
												a__             =     model(__snake_case      )
												self.parent.assertEqual(result.last_hidden_state.shape			,(self.batch_size, self.seq_length, self.hidden_size)      )
					def  lowerCamelCase__(      self   :Dict			,__snake_case   :List[str]			,__snake_case   :List[Any]			,__snake_case   :Any      )					->    str:
												a__             =     TimesformerForVideoClassification(__snake_case      )
												model.to(__snake_case      )
												model.eval()

												a__             =     model(__snake_case      )

												# verify the logits shape
												a__             =     torch.Size((self.batch_size, self.num_labels)      )
												self.parent.assertEqual(result.logits.shape			,__snake_case      )



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







@require_torch
class        snake_case_   (lowerCamelCase_	,						lowerCamelCase_	,						unittest.TestCase      ):
					UpperCAmelCase__					:    List[Any]          =			(TimesformerModel, TimesformerForVideoClassification) if is_torch_available() else ()
					UpperCAmelCase__					:    str          =			(
					    {'''feature-extraction''': TimesformerModel, '''video-classification''': TimesformerForVideoClassification}
					    if is_torch_available()
					    else {}
					)

					UpperCAmelCase__					:    Tuple          =			False
					UpperCAmelCase__					:    str          =			False
					UpperCAmelCase__					:    int          =			False
					UpperCAmelCase__					:    Optional[int]          =			False
					def  lowerCamelCase__(      self   :Optional[Any]      )					->    int:
												a__             =     TimesformerModelTester(self      )
												a__             =     ConfigTester(
												    self			,config_class=__snake_case			,has_text_modality=__snake_case			,hidden_size=37      )
					def  lowerCamelCase__(      self   :int			,__snake_case   :List[Any]			,__snake_case   :Optional[int]			,__snake_case   :Optional[int]=False      )					->    str:
												a__             =     copy.deepcopy(__snake_case      )

												if return_labels:
																			if model_class in get_values(__snake_case      ):
																										a__             =     torch.zeros(
																										    self.model_tester.batch_size			,dtype=torch.long			,device=__snake_case      )

												return inputs_dict
					def  lowerCamelCase__(      self   :Dict      )					->    List[str]:
												self.config_tester.run_common_tests()
					@unittest.skip(reason='TimeSformer does not use inputs_embeds'      )
					def  lowerCamelCase__(      self   :str      )					->    int:
												pass
					def  lowerCamelCase__(      self   :List[Any]      )					->    str:
												a__      ,					a__             =     self.model_tester.prepare_config_and_inputs_for_common()

												for model_class in self.all_model_classes:
																			a__             =     model_class(__snake_case      )
																			self.assertIsInstance(model.get_input_embeddings()			,(nn.Module)      )
																			a__             =     model.get_output_embeddings()
																			self.assertTrue(x is None or isinstance(__snake_case			,nn.Linear      )      )
					def  lowerCamelCase__(      self   :List[str]      )					->    Optional[Any]:
												a__      ,					a__             =     self.model_tester.prepare_config_and_inputs_for_common()

												for model_class in self.all_model_classes:
																			a__             =     model_class(__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]			,__snake_case      )
					def  lowerCamelCase__(      self   :Dict      )					->    Dict:
												a__             =     self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_model(*__snake_case      )
					def  lowerCamelCase__(      self   :int      )					->    Union[str, Any]:
												a__             =     self.model_tester.prepare_config_and_inputs()
												self.model_tester.create_and_check_for_video_classification(*__snake_case      )
					@slow
					def  lowerCamelCase__(      self   :Optional[Any]      )					->    Dict:
												for model_name in TIMESFORMER_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
																			a__             =     TimesformerModel.from_pretrained(__snake_case      )
																			self.assertIsNotNone(__snake_case      )
					def  lowerCamelCase__(      self   :int      )					->    Tuple:
												if not self.has_attentions:
																			pass

												else:
																			a__      ,					a__             =     self.model_tester.prepare_config_and_inputs_for_common()
																			a__             =     True

																			for model_class in self.all_model_classes:
																										a__             =     self.model_tester.seq_length
																										a__             =     self.model_tester.num_frames

																										a__             =     True
																										a__             =     False
																										a__             =     True
																										a__             =     model_class(__snake_case      )
																										model.to(__snake_case      )
																										model.eval()
																										with torch.no_grad():
																																	a__             =     model(**self._prepare_for_class(__snake_case			,__snake_case      )      )
																										a__             =     outputs.attentions
																										self.assertEqual(len(__snake_case      )			,self.model_tester.num_hidden_layers      )

																										# check that output_attentions also work using config
																										del inputs_dict["output_attentions"]
																										a__             =     True
																										a__             =     model_class(__snake_case      )
																										model.to(__snake_case      )
																										model.eval()
																										with torch.no_grad():
																																	a__             =     model(**self._prepare_for_class(__snake_case			,__snake_case      )      )
																										a__             =     outputs.attentions
																										self.assertEqual(len(__snake_case      )			,self.model_tester.num_hidden_layers      )

																										# attentions has shape (batch_size x num_frames) x num_heads x (num_patches per frame + 1) x (num_patches per frame + 1)
																										self.assertListEqual(
																										    list(attentions[0].shape[-3:]      )			,[self.model_tester.num_attention_heads, seq_len // num_frames + 1, seq_len // num_frames + 1]			,)
																										a__             =     len(__snake_case      )

																										# Check attention is always last and order is fine
																										a__             =     True
																										a__             =     True
																										a__             =     model_class(__snake_case      )
																										model.to(__snake_case      )
																										model.eval()
																										with torch.no_grad():
																																	a__             =     model(**self._prepare_for_class(__snake_case			,__snake_case      )      )

																										self.assertEqual(out_len + 1			,len(__snake_case      )      )

																										a__             =     outputs.attentions

																										self.assertEqual(len(__snake_case      )			,self.model_tester.num_hidden_layers      )

																										# attentions has shape (batch_size x num_frames) x num_heads x (num_patches per frame + 1) x (num_patches per frame + 1)
																										self.assertListEqual(
																										    list(self_attentions[0].shape[-3:]      )			,[self.model_tester.num_attention_heads, seq_len // num_frames + 1, seq_len // num_frames + 1]			,)



					def  lowerCamelCase__(      self   :List[Any]      )					->    Dict:
												def check_hidden_states_output(__snake_case   :List[str]			,__snake_case   :str			,__snake_case   :Optional[Any]      ):
																			a__             =     model_class(__snake_case      )
																			model.to(__snake_case      )
																			model.eval()

																			with torch.no_grad():
																										a__             =     model(**self._prepare_for_class(__snake_case			,__snake_case      )      )

																			a__             =     outputs.hidden_states
																			a__             =     self.model_tester.num_hidden_layers + 1
																			self.assertEqual(len(__snake_case      )			,__snake_case      )

																			a__             =     self.model_tester.seq_length

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

												a__      ,					a__             =     self.model_tester.prepare_config_and_inputs_for_common()

												for model_class in self.all_model_classes:
																			a__             =     True
																			check_hidden_states_output(__snake_case			,__snake_case			,__snake_case      )

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

																			check_hidden_states_output(__snake_case			,__snake_case			,__snake_case      )






def 							__lowercase   ( ):
							a__             =     hf_hub_download(
							    repo_id='hf-internal-testing/spaghetti-video'					,    filename='eating_spaghetti.npy'					,    repo_type='dataset'   )
							a__             =     np.load(__lowerCAmelCase   )
							return list(__lowerCAmelCase   )







@require_torch
@require_vision
class        snake_case_   (unittest.TestCase      ):
					@cached_property
					def  lowerCamelCase__(      self   :Optional[int]      )					->    int:
												# logits were tested with a different mean and std, so we use the same here
												return (
												    VideoMAEImageProcessor(image_mean=[0.5, 0.5, 0.5]			,image_std=[0.5, 0.5, 0.5]      )
												    if is_vision_available()
												    else None
												)



					@slow
					def  lowerCamelCase__(      self   :Tuple      )					->    Dict:
												a__             =     TimesformerForVideoClassification.from_pretrained('facebook/timesformer-base-finetuned-k400'      ).to(
												    __snake_case      )

												a__             =     self.default_image_processor
												a__             =     prepare_video()
												a__             =     image_processor(video[:8]			,return_tensors='pt'      ).to(__snake_case      )

												# forward pass
												with torch.no_grad():
																			a__             =     model(**__snake_case      )

												# verify the logits
												a__             =     torch.Size((1, 4_00)      )
												self.assertEqual(outputs.logits.shape			,__snake_case      )

												a__             =     torch.tensor([-0.30_16, -0.77_13, -0.42_05]      ).to(__snake_case      )

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








import math






def 							__lowercase   ( __lowerCAmelCase							:				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					,    __lowerCAmelCase					,    2   ):
														if is_prime[i]:
																					primes.append(__lowerCAmelCase   )

							return primes






def 							__lowercase   ( __lowerCAmelCase							:				int = 9_9_9_9_6_6_6_6_3_3_3_3   ):
							a__             =     math.floor(math.sqrt(__lowerCAmelCase   )   ) + 1_0_0
							a__             =     prime_sieve(__lowerCAmelCase   )

							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())




