
"""simple docstring"""


def    lowercase	(  lowerCAmelCase__ = 4_000_000	):







			if n <= 1:
						return 0
			lowerCamelCase_ 		=     0
			lowerCamelCase_ 		=     2
			lowerCamelCase_ 		=     0
			while 4 * b + a <= n:
						lowerCamelCase_		,   lowerCamelCase_ 		=     b, 4 * b + a
						count += a
			return count + b


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








"""simple docstring"""


import tempfile
import unittest

import torch

from diffusers import UNetaDConditionModel
from diffusers.training_utils import EMAModel
from diffusers.utils.testing_utils import enable_full_determinism, skip_mps, torch_device


enable_full_determinism()




class    __lowerCamelCase     (   unittest.TestCase ):
				a__:			Union[str, Any]									=						'hf-internal-testing/tiny-stable-diffusion-pipe'
				a__:			Tuple									=						1
				a__:			int									=						77
				a__:			List[str]									=						32
				a__:			List[Any]									=						4
				a__:			str									=						64
				a__:			Optional[Any]									=						torch.manual_seed(0 )




				def 					UpperCAmelCase__	(							self       ,	UpperCAmelCase=0.9_9_9_9      ):
							lowerCamelCase_ 		=     UNetaDConditionModel.from_pretrained(self.model_id       ,	subfolder='''unet'''      )
							lowerCamelCase_ 		=     unet.to(UpperCAmelCase      )
							lowerCamelCase_ 		=     EMAModel(unet.parameters()       ,	decay=UpperCAmelCase       ,	model_cls=UpperCAmelCase       ,	model_config=unet.config      )
							return unet, ema_unet




				def 					UpperCAmelCase__	(							self      ):
							lowerCamelCase_ 		=     torch.randn(
							    self.batch_size       ,	self.num_in_channels       ,	self.latent_height       ,	self.latent_width       ,	generator=self.generator      ).to(UpperCAmelCase      )
							lowerCamelCase_ 		=     torch.randint(0       ,	1000       ,	size=(self.batch_size,)       ,	generator=self.generator      ).to(UpperCAmelCase      )
							lowerCamelCase_ 		=     torch.randn(
							    self.batch_size       ,	self.prompt_length       ,	self.text_encoder_hidden_dim       ,	generator=self.generator      ).to(UpperCAmelCase      )
							return noisy_latents, timesteps, encoder_hidden_states




				def 					UpperCAmelCase__	(							self       ,	UpperCAmelCase      ):
							lowerCamelCase_ 		=     {}
							for k, param in unet.state_dict().items():
										lowerCamelCase_ 		=     torch.randn_like(UpperCAmelCase      ) + (param * torch.randn_like(UpperCAmelCase      ))
										updated_state_dict.update({k: updated_param}      )
							unet.load_state_dict(UpperCAmelCase      )
							return unet




				def 					UpperCAmelCase__	(							self      ):
							lowerCamelCase_		,   lowerCamelCase_ 		=     self.get_models()
							# Take the first (hypothetical) EMA step.
							ema_unet.step(unet.parameters()      )
							assert ema_unet.optimization_step == 1

							# Take two more.
							for _ in range(2      ):
										ema_unet.step(unet.parameters()      )
							assert ema_unet.optimization_step == 3




				def 					UpperCAmelCase__	(							self      ):
							lowerCamelCase_		,   lowerCamelCase_ 		=     self.get_models()
							# Since the `unet` is not being updated (i.e., backprop'd)
							# there won't be any difference between the `params` of `unet`
							# and `ema_unet` even if we call `ema_unet.step(unet.parameters())`.
							ema_unet.step(unet.parameters()      )
							lowerCamelCase_ 		=     list(unet.parameters()      )
							for s_param, param in zip(ema_unet.shadow_params       ,	UpperCAmelCase      ):
										assert torch.allclose(UpperCAmelCase       ,	UpperCAmelCase      )

							# The above holds true even if we call `ema.step()` multiple times since
							# `unet` params are still not being updated.
							for _ in range(4      ):
										ema_unet.step(unet.parameters()      )
							for s_param, param in zip(ema_unet.shadow_params       ,	UpperCAmelCase      ):
										assert torch.allclose(UpperCAmelCase       ,	UpperCAmelCase      )




				def 					UpperCAmelCase__	(							self      ):
							lowerCamelCase_		,   lowerCamelCase_ 		=     self.get_models()
							# Here we simulate the parameter updates for `unet`. Since there might
							# be some parameters which are initialized to zero we take extra care to
							# initialize their values to something non-zero before the multiplication.
							lowerCamelCase_ 		=     self.simulate_backprop(UpperCAmelCase      )

							# Take the EMA step.
							ema_unet.step(unet_pseudo_updated_step_one.parameters()      )

							# Now the EMA'd parameters won't be equal to the original model parameters.
							lowerCamelCase_ 		=     list(unet_pseudo_updated_step_one.parameters()      )
							for s_param, param in zip(ema_unet.shadow_params       ,	UpperCAmelCase      ):
										assert ~torch.allclose(UpperCAmelCase       ,	UpperCAmelCase      )

							# Ensure this is the case when we take multiple EMA steps.
							for _ in range(4      ):
										ema_unet.step(unet.parameters()      )
							for s_param, param in zip(ema_unet.shadow_params       ,	UpperCAmelCase      ):
										assert ~torch.allclose(UpperCAmelCase       ,	UpperCAmelCase      )




				def 					UpperCAmelCase__	(							self      ):
							# If we call EMA step after a backpropagation consecutively for two times,
							# the shadow params from those two steps should be different.
							lowerCamelCase_		,   lowerCamelCase_ 		=     self.get_models()

							# First backprop + EMA
							lowerCamelCase_ 		=     self.simulate_backprop(UpperCAmelCase      )
							ema_unet.step(unet_step_one.parameters()      )
							lowerCamelCase_ 		=     ema_unet.shadow_params

							# Second backprop + EMA
							lowerCamelCase_ 		=     self.simulate_backprop(UpperCAmelCase      )
							ema_unet.step(unet_step_two.parameters()      )
							lowerCamelCase_ 		=     ema_unet.shadow_params

							for step_one, step_two in zip(UpperCAmelCase       ,	UpperCAmelCase      ):
										assert ~torch.allclose(UpperCAmelCase       ,	UpperCAmelCase      )




				def 					UpperCAmelCase__	(							self      ):
							# If there's no decay even if there are backprops, EMA steps
							# won't take any effect i.e., the shadow params would remain the
							# same.
							lowerCamelCase_		,   lowerCamelCase_ 		=     self.get_models(decay=0.0      )
							lowerCamelCase_ 		=     self.simulate_backprop(UpperCAmelCase      )
							ema_unet.step(unet_step_one.parameters()      )
							lowerCamelCase_ 		=     ema_unet.shadow_params

							lowerCamelCase_ 		=     self.simulate_backprop(UpperCAmelCase      )
							ema_unet.step(unet_step_two.parameters()      )
							lowerCamelCase_ 		=     ema_unet.shadow_params

							for step_one, step_two in zip(UpperCAmelCase       ,	UpperCAmelCase      ):
										assert torch.allclose(UpperCAmelCase       ,	UpperCAmelCase      )





				@skip_mps
				def 					UpperCAmelCase__	(							self      ):
							lowerCamelCase_		,   lowerCamelCase_ 		=     self.get_models()
							lowerCamelCase_		,   lowerCamelCase_		,   lowerCamelCase_ 		=     self.get_dummy_inputs()

							with tempfile.TemporaryDirectory() as tmpdir:
										ema_unet.save_pretrained(UpperCAmelCase      )
										lowerCamelCase_ 		=     UNetaDConditionModel.from_pretrained(UpperCAmelCase       ,	model_cls=UpperCAmelCase      )
										lowerCamelCase_ 		=     loaded_unet.to(unet.device      )

							# Since no EMA step has been performed the outputs should match.
							lowerCamelCase_ 		=     unet(UpperCAmelCase       ,	UpperCAmelCase       ,	UpperCAmelCase      ).sample
							lowerCamelCase_ 		=     loaded_unet(UpperCAmelCase       ,	UpperCAmelCase       ,	UpperCAmelCase      ).sample

							assert torch.allclose(UpperCAmelCase       ,	UpperCAmelCase       ,	atol=1e-4      )



