

import math







def 						SCREAMING_SNAKE_CASE(  UpperCamelCase  )    ->    Optional[int]:
	UpperCAmelCase_		:      int       	=					[]
	UpperCAmelCase_		:      str       	=					2
	UpperCAmelCase_		:      Any       	=					int(math.sqrt(UpperCAmelCase__  )  )  # Size of every segment
	UpperCAmelCase_		:      int       	=					[True] * (end + 1)
	UpperCAmelCase_		:      Optional[Any]       	=					[]

	while start <= end:
		if temp[start] is True:
			in_prime.append(UpperCAmelCase__  )
			for i in range(start * start   ,end + 1   ,UpperCAmelCase__  ):
				UpperCAmelCase_		:      Tuple       	=					False
		start += 1
	prime += in_prime

	UpperCAmelCase_		:      List[Any]       	=					end + 1
	UpperCAmelCase_		:      List[Any]       	=					min(2 * end   ,UpperCAmelCase__  )

	while low <= n:
		UpperCAmelCase_		:      List[Any]       	=					[True] * (high - low + 1)
		for each in in_prime:
			UpperCAmelCase_		:      Any       	=					math.floor(low / each  ) * each
			if t < low:
				t += each

			for j in range(UpperCAmelCase__   ,high + 1   ,UpperCAmelCase__  ):
				UpperCAmelCase_		:      List[Any]       	=					False

		for j in range(len(UpperCAmelCase__  )  ):
			if temp[j] is True:
				prime.append(j + low  )

		UpperCAmelCase_		:      Dict       	=					high + 1
		UpperCAmelCase_		:      Dict       	=					min(high + end   ,UpperCAmelCase__  )

	return prime







print(sieve(10**6))









'''simple docstring'''


import unittest

import numpy as np
import timeout_decorator  # noqa

from transformers import BlenderbotSmallConfig, is_flax_available
from transformers.testing_utils import require_flax, slow

from ...generation.test_flax_utils import FlaxGenerationTesterMixin
from ...test_modeling_flax_common import FlaxModelTesterMixin, ids_tensor


if is_flax_available():
						import os

						# The slow tests are often failing with OOM error on GPU
						# This makes JAX allocate exactly what is needed on demand, and deallocate memory that is no longer needed
						# but will be slower as stated here https://jax.readthedocs.io/en/latest/gpu_memory_allocation.html
						lowerCAmelCase__										= "platform"

						import jax
						import jax.numpy as jnp

						from transformers.models.blenderbot_small.modeling_flax_blenderbot_small import (
						    FlaxBlenderbotSmallForConditionalGeneration,
						    FlaxBlenderbotSmallModel,
						    shift_tokens_right,
						)







def 						SCREAMING_SNAKE_CASE(  UpperCamelCase   ,UpperCamelCase   ,UpperCamelCase=None   ,UpperCamelCase=None   ,UpperCamelCase=None   ,UpperCamelCase=None   ,UpperCamelCase=None   ,UpperCamelCase=None   ,)    ->    List[Any]:
	if attention_mask is None:
		UpperCAmelCase_		:      Tuple       	=					np.where(input_ids != config.pad_token_id   ,1   ,0  )
	if decoder_attention_mask is None:
		UpperCAmelCase_		:      List[str]       	=					np.where(decoder_input_ids != config.pad_token_id   ,1   ,0  )
	if head_mask is None:
		UpperCAmelCase_		:      Optional[Any]       	=					np.ones((config.encoder_layers, config.encoder_attention_heads)  )
	if decoder_head_mask is None:
		UpperCAmelCase_		:      Optional[int]       	=					np.ones((config.decoder_layers, config.decoder_attention_heads)  )
	if cross_attn_head_mask is None:
		UpperCAmelCase_		:      List[str]       	=					np.ones((config.decoder_layers, config.decoder_attention_heads)  )
	return {
	    "input_ids": input_ids,
	    "decoder_input_ids": decoder_input_ids,
	    "attention_mask": attention_mask,
	    "decoder_attention_mask": attention_mask,
	}



class 					lowercase						:


							def __init__(			self    ,			_snake_case    ,			_snake_case=13    ,			_snake_case=7    ,			_snake_case=True    ,			_snake_case=False    ,			_snake_case=99    ,			_snake_case=16    ,			_snake_case=2    ,			_snake_case=4    ,			_snake_case=4    ,			_snake_case="gelu"    ,			_snake_case=0.1    ,			_snake_case=0.1    ,			_snake_case=32    ,			_snake_case=2    ,			_snake_case=1    ,			_snake_case=0    ,			_snake_case=0.02    ,			)							->				int:
								UpperCAmelCase_		:      List[Any]       	=					parent
								UpperCAmelCase_		:      Optional[int]       	=					batch_size
								UpperCAmelCase_		:      Tuple       	=					seq_length
								UpperCAmelCase_		:      List[Any]       	=					is_training
								UpperCAmelCase_		:      int       	=					use_labels
								UpperCAmelCase_		:      List[str]       	=					vocab_size
								UpperCAmelCase_		:      Dict       	=					hidden_size
								UpperCAmelCase_		:      int       	=					num_hidden_layers
								UpperCAmelCase_		:      int       	=					num_attention_heads
								UpperCAmelCase_		:      int       	=					intermediate_size
								UpperCAmelCase_		:      Dict       	=					hidden_act
								UpperCAmelCase_		:      str       	=					hidden_dropout_prob
								UpperCAmelCase_		:      Any       	=					attention_probs_dropout_prob
								UpperCAmelCase_		:      int       	=					max_position_embeddings
								UpperCAmelCase_		:      Optional[Any]       	=					eos_token_id
								UpperCAmelCase_		:      Tuple       	=					pad_token_id
								UpperCAmelCase_		:      List[Any]       	=					bos_token_id
								UpperCAmelCase_		:      Optional[int]       	=					initializer_range


							def 						_snake_case							(			self)							->				Any:
								UpperCAmelCase_		:      int       	=					np.clip(ids_tensor([self.batch_size, self.seq_length - 1]    ,			self.vocab_size)    ,			3    ,			self.vocab_size)
								UpperCAmelCase_		:      List[str]       	=					np.concatenate((input_ids, 2 * np.ones((self.batch_size, 1)    ,			dtype=np.intaa))    ,			-1)

								UpperCAmelCase_		:      Optional[int]       	=					shift_tokens_right(_snake_case    ,			1    ,			2)

								UpperCAmelCase_		:      Dict       	=					BlenderbotSmallConfig(
								    vocab_size=self.vocab_size    ,			d_model=self.hidden_size    ,			encoder_layers=self.num_hidden_layers    ,			decoder_layers=self.num_hidden_layers    ,			encoder_attention_heads=self.num_attention_heads    ,			decoder_attention_heads=self.num_attention_heads    ,			encoder_ffn_dim=self.intermediate_size    ,			decoder_ffn_dim=self.intermediate_size    ,			dropout=self.hidden_dropout_prob    ,			attention_dropout=self.attention_probs_dropout_prob    ,			max_position_embeddings=self.max_position_embeddings    ,			eos_token_id=self.eos_token_id    ,			bos_token_id=self.bos_token_id    ,			pad_token_id=self.pad_token_id    ,			initializer_range=self.initializer_range    ,			use_cache=_snake_case    ,			)
								UpperCAmelCase_		:      List[Any]       	=					prepare_blenderbot_inputs_dict(_snake_case    ,			_snake_case    ,			_snake_case)
								return config, inputs_dict


							def 						_snake_case							(			self)							->				int:
								UpperCAmelCase_	,    UpperCAmelCase_		:      Dict       	=					self.prepare_config_and_inputs()
								return config, inputs_dict


							def 						_snake_case							(			self    ,			_snake_case    ,			_snake_case    ,			_snake_case)							->				Tuple:
								UpperCAmelCase_		:      Optional[Any]       	=					20
								UpperCAmelCase_		:      str       	=					model_class_name(_snake_case)

								UpperCAmelCase_		:      Dict       	=					model.encode(inputs_dict['input_ids'])

								UpperCAmelCase_	,    UpperCAmelCase_		:      Union[str, Any]       	=					(
								    inputs_dict['decoder_input_ids'],
								    inputs_dict['decoder_attention_mask'],
								)

								UpperCAmelCase_		:      Optional[int]       	=					model.init_cache(decoder_input_ids.shape[0]    ,			_snake_case    ,			_snake_case)
								UpperCAmelCase_		:      List[Any]       	=					jnp.ones((decoder_input_ids.shape[0], max_decoder_length)    ,			dtype='i4')

								UpperCAmelCase_		:      Dict       	=					jnp.broadcast_to(
								    jnp.arange(decoder_input_ids.shape[-1] - 1)[None, :]    ,			(decoder_input_ids.shape[0], decoder_input_ids.shape[-1] - 1)    ,			)
								UpperCAmelCase_		:      Optional[int]       	=					model.decode(
								    decoder_input_ids[:, :-1]    ,			_snake_case    ,			decoder_attention_mask=_snake_case    ,			past_key_values=_snake_case    ,			decoder_position_ids=_snake_case    ,			)

								UpperCAmelCase_		:      int       	=					jnp.array(decoder_input_ids.shape[0] * [[decoder_input_ids.shape[-1] - 1]]    ,			dtype='i4')
								UpperCAmelCase_		:      Any       	=					model.decode(
								    decoder_input_ids[:, -1:]    ,			_snake_case    ,			decoder_attention_mask=_snake_case    ,			past_key_values=outputs_cache.past_key_values    ,			decoder_position_ids=_snake_case    ,			)

								UpperCAmelCase_		:      Optional[int]       	=					model.decode(_snake_case    ,			_snake_case)

								UpperCAmelCase_		:      List[str]       	=					np.max(np.abs((outputs_cache_next[0][:, -1, :5] - outputs[0][:, -1, :5])))
								self.parent.assertTrue(diff < 1e-3    ,			msg=F"""Max diff is {diff}""")





							def 						_snake_case							(			self    ,			_snake_case    ,			_snake_case    ,			_snake_case)							->				int:
								UpperCAmelCase_		:      int       	=					20
								UpperCAmelCase_		:      Optional[int]       	=					model_class_name(_snake_case)

								UpperCAmelCase_		:      Optional[int]       	=					model.encode(inputs_dict['input_ids'])

								UpperCAmelCase_	,    UpperCAmelCase_		:      Tuple       	=					(
								    inputs_dict['decoder_input_ids'],
								    inputs_dict['decoder_attention_mask'],
								)

								UpperCAmelCase_		:      int       	=					jnp.concatenate(
								    [
								        decoder_attention_mask,
								        jnp.zeros((decoder_attention_mask.shape[0], max_decoder_length - decoder_attention_mask.shape[1])),
								    ]    ,			axis=-1    ,			)

								UpperCAmelCase_		:      Any       	=					model.init_cache(decoder_input_ids.shape[0]    ,			_snake_case    ,			_snake_case)
								UpperCAmelCase_		:      Optional[int]       	=					jnp.broadcast_to(
								    jnp.arange(decoder_input_ids.shape[-1] - 1)[None, :]    ,			(decoder_input_ids.shape[0], decoder_input_ids.shape[-1] - 1)    ,			)

								UpperCAmelCase_		:      Optional[int]       	=					model.decode(
								    decoder_input_ids[:, :-1]    ,			_snake_case    ,			decoder_attention_mask=_snake_case    ,			past_key_values=_snake_case    ,			decoder_position_ids=_snake_case    ,			)
								UpperCAmelCase_		:      List[Any]       	=					jnp.array(decoder_input_ids.shape[0] * [[decoder_input_ids.shape[-1] - 1]]    ,			dtype='i4')
								UpperCAmelCase_		:      Dict       	=					model.decode(
								    decoder_input_ids[:, -1:]    ,			_snake_case    ,			past_key_values=outputs_cache.past_key_values    ,			decoder_attention_mask=_snake_case    ,			decoder_position_ids=_snake_case    ,			)

								UpperCAmelCase_		:      Any       	=					model.decode(_snake_case    ,			_snake_case    ,			decoder_attention_mask=_snake_case)

								UpperCAmelCase_		:      Dict       	=					np.max(np.abs((outputs_cache_next[0][:, -1, :5] - outputs[0][:, -1, :5])))
								self.parent.assertTrue(diff < 1e-3    ,			msg=F"""Max diff is {diff}""")



@require_flax
class 					lowercase						(  unittest.TestCase ):
							_lowerCamelCase		:      Union[str, Any]=   99


							def 						_snake_case							(			self)							->				int:
								UpperCAmelCase_		:      str       	=					np.array(
								    [
								        [71, 82, 18, 33, 46, 91, 2],
								        [68, 34, 26, 58, 30, 82, 2],
								        [5, 97, 17, 39, 94, 40, 2],
								        [76, 83, 94, 25, 70, 78, 2],
								        [87, 59, 41, 35, 48, 66, 2],
								        [55, 13, 16, 58, 5, 2, 1],  # note padding
								        [64, 27, 31, 51, 12, 75, 2],
								        [52, 64, 86, 17, 83, 39, 2],
								        [48, 61, 9, 24, 71, 82, 2],
								        [26, 1, 60, 48, 22, 13, 2],
								        [21, 5, 62, 28, 14, 76, 2],
								        [45, 98, 37, 86, 59, 48, 2],
								        [70, 70, 50, 9, 28, 0, 2],
								    ]    ,			dtype=np.intaa    ,			)

								UpperCAmelCase_		:      Optional[int]       	=					input_ids.shape[0]
								UpperCAmelCase_		:      Any       	=					BlenderbotSmallConfig(
								    vocab_size=self.vocab_size    ,			d_model=24    ,			encoder_layers=2    ,			decoder_layers=2    ,			encoder_attention_heads=2    ,			decoder_attention_heads=2    ,			encoder_ffn_dim=32    ,			decoder_ffn_dim=32    ,			max_position_embeddings=48    ,			eos_token_id=2    ,			pad_token_id=1    ,			bos_token_id=0    ,			)
								return config, input_ids, batch_size


							def 						_snake_case							(			self)							->				Optional[Any]:
								UpperCAmelCase_	,    UpperCAmelCase_	,    UpperCAmelCase_		:      int       	=					self._get_config_and_data()
								UpperCAmelCase_		:      str       	=					FlaxBlenderbotSmallForConditionalGeneration(_snake_case)
								UpperCAmelCase_		:      Union[str, Any]       	=					lm_model(input_ids=_snake_case)
								UpperCAmelCase_		:      str       	=					(batch_size, input_ids.shape[1], config.vocab_size)
								self.assertEqual(outputs['logits'].shape    ,			_snake_case)


							def 						_snake_case							(			self)							->				Tuple:
								UpperCAmelCase_		:      Tuple       	=					BlenderbotSmallConfig(
								    vocab_size=self.vocab_size    ,			d_model=14    ,			encoder_layers=2    ,			decoder_layers=2    ,			encoder_attention_heads=2    ,			decoder_attention_heads=2    ,			encoder_ffn_dim=8    ,			decoder_ffn_dim=8    ,			max_position_embeddings=48    ,			)
								UpperCAmelCase_		:      Union[str, Any]       	=					FlaxBlenderbotSmallForConditionalGeneration(_snake_case)
								UpperCAmelCase_		:      Dict       	=					np.array([[71, 82, 18, 33, 46, 91, 2], [68, 34, 26, 58, 30, 2, 1]]    ,			dtype=np.intaa)
								UpperCAmelCase_		:      Union[str, Any]       	=					np.array([[82, 71, 82, 18, 2], [58, 68, 2, 1, 1]]    ,			dtype=np.intaa)
								UpperCAmelCase_		:      List[str]       	=					lm_model(input_ids=_snake_case    ,			decoder_input_ids=_snake_case)
								UpperCAmelCase_		:      Optional[Any]       	=					(*summary.shape, config.vocab_size)
								self.assertEqual(outputs['logits'].shape    ,			_snake_case)





							def 						_snake_case							(			self)							->				Optional[Any]:
								UpperCAmelCase_		:      int       	=					np.array([[71, 82, 18, 33, 2, 1, 1], [68, 34, 26, 58, 30, 82, 2]]    ,			dtype=np.intaa)
								UpperCAmelCase_		:      List[str]       	=					shift_tokens_right(_snake_case    ,			1    ,			2)
								UpperCAmelCase_		:      Dict       	=					np.equal(_snake_case    ,			1).astype(np.floataa).sum()
								UpperCAmelCase_		:      Union[str, Any]       	=					np.equal(_snake_case    ,			1).astype(np.floataa).sum()
								self.assertEqual(shifted.shape    ,			input_ids.shape)
								self.assertEqual(_snake_case    ,			n_pad_before - 1)
								self.assertTrue(np.equal(shifted[:, 0]    ,			2).all())



@require_flax
class 					lowercase						(  a_,					unittest.TestCase,					a_ ):
							_lowerCamelCase		:      str=   True
							_lowerCamelCase		:      Union[str, Any]=   (
							    (
							        FlaxBlenderbotSmallModel,
							        FlaxBlenderbotSmallForConditionalGeneration,
							    )
							    if is_flax_available()
							    else ()
							)
							_lowerCamelCase		:      Optional[int]=   (FlaxBlenderbotSmallForConditionalGeneration,) if is_flax_available() else ()


							def 						_snake_case							(			self)							->				Optional[Any]:
								UpperCAmelCase_		:      List[str]       	=					FlaxBlenderbotSmallModelTester(self)


							def 						_snake_case							(			self)							->				str:
								UpperCAmelCase_	,    UpperCAmelCase_		:      Any       	=					self.model_tester.prepare_config_and_inputs()
								for model_class in self.all_model_classes:
									self.model_tester.check_use_cache_forward(_snake_case    ,			_snake_case    ,			_snake_case)


							def 						_snake_case							(			self)							->				List[str]:
								UpperCAmelCase_	,    UpperCAmelCase_		:      str       	=					self.model_tester.prepare_config_and_inputs()
								for model_class in self.all_model_classes:
									self.model_tester.check_use_cache_forward_with_attn_mask(_snake_case    ,			_snake_case    ,			_snake_case)


							def 						_snake_case							(			self)							->				Union[str, Any]:
								UpperCAmelCase_	,    UpperCAmelCase_		:      Optional[Any]       	=					self.model_tester.prepare_config_and_inputs_for_common()

								for model_class in self.all_model_classes:
									with self.subTest(model_class.__name__):
										UpperCAmelCase_		:      Dict       	=					self._prepare_for_class(_snake_case    ,			_snake_case)
										UpperCAmelCase_		:      Union[str, Any]       	=					model_class(_snake_case)

										@jax.jit
										def encode_jitted(_snake_case    ,			_snake_case=None    ,			**_snake_case):
											return model.encode(input_ids=_snake_case    ,			attention_mask=_snake_case)

										with self.subTest('JIT Enabled'):
											UpperCAmelCase_		:      Optional[int]       	=					encode_jitted(**_snake_case).to_tuple()

										with self.subTest('JIT Disabled'):
											with jax.disable_jit():
												UpperCAmelCase_		:      Optional[int]       	=					encode_jitted(**_snake_case).to_tuple()

										self.assertEqual(len(_snake_case)    ,			len(_snake_case))
										for jitted_output, output in zip(_snake_case    ,			_snake_case):
											self.assertEqual(jitted_output.shape    ,			output.shape)


							def 						_snake_case							(			self)							->				Optional[Any]:
								UpperCAmelCase_	,    UpperCAmelCase_		:      Optional[int]       	=					self.model_tester.prepare_config_and_inputs_for_common()

								for model_class in self.all_model_classes:
									with self.subTest(model_class.__name__):
										UpperCAmelCase_		:      Tuple       	=					model_class(_snake_case)
										UpperCAmelCase_		:      Union[str, Any]       	=					model.encode(inputs_dict['input_ids']    ,			inputs_dict['attention_mask'])

										UpperCAmelCase_		:      str       	=					{
										    'decoder_input_ids': inputs_dict['decoder_input_ids'],
										    'decoder_attention_mask': inputs_dict['decoder_attention_mask'],
										    'encoder_outputs': encoder_outputs,
										}

										@jax.jit
										def decode_jitted(_snake_case    ,			_snake_case    ,			_snake_case):
											return model.decode(
											    decoder_input_ids=_snake_case    ,			decoder_attention_mask=_snake_case    ,			encoder_outputs=_snake_case    ,			)

										with self.subTest('JIT Enabled'):
											UpperCAmelCase_		:      Tuple       	=					decode_jitted(**_snake_case).to_tuple()

										with self.subTest('JIT Disabled'):
											with jax.disable_jit():
												UpperCAmelCase_		:      List[Any]       	=					decode_jitted(**_snake_case).to_tuple()

										self.assertEqual(len(_snake_case)    ,			len(_snake_case))
										for jitted_output, output in zip(_snake_case    ,			_snake_case):
											self.assertEqual(jitted_output.shape    ,			output.shape)





							@slow
							def 						_snake_case							(			self)							->				Any:
								for model_class_name in self.all_model_classes:
									UpperCAmelCase_		:      Any       	=					model_class_name.from_pretrained('facebook/blenderbot_small-90M')
									# FlaxBlenderbotForSequenceClassification expects eos token in input_ids
									UpperCAmelCase_		:      List[Any]       	=					np.ones((1, 1)) * model.config.eos_token_id
									UpperCAmelCase_		:      Dict       	=					model(_snake_case)
									self.assertIsNotNone(_snake_case)






