





"""simple docstring"""




import inspect
import logging
import os
import random
import shutil
import tempfile
import unittest

import pytest
import torch
from torch import nn
from torch.utils.data import DataLoader, TensorDataset

from accelerate import Accelerator
from accelerate.test_utils import execute_subprocess_async, require_cuda
from accelerate.utils import ProjectConfiguration, set_seed


lowerCAmelCase							:    int  							=							logging.getLogger(__name__)



def 					a__				(       snake_case__=2 ,				snake_case__=3 ,				snake_case__=16 ,				snake_case__ = 10 ,				snake_case__ = 2       )		->      Optional[int]:

			def get_dataset(snake_case__       ):
						lowerCamelCase       =      torch.randn(batch_size * n_batches ,				1       )
						return TensorDataset(snake_case__ ,				a * x + b + 0.1 * torch.randn(batch_size * n_batches ,				1       )       )

			lowerCamelCase       =      get_dataset(snake_case__       )
			lowerCamelCase       =      get_dataset(snake_case__       )
			lowerCamelCase       =      DataLoader(snake_case__ ,				shuffle=snake_case__ ,				batch_size=snake_case__ ,				num_workers=4       )
			lowerCamelCase       =      DataLoader(snake_case__ ,				shuffle=snake_case__ ,				batch_size=snake_case__ ,				num_workers=4       )
			return (train_dataloader, valid_dataloader)



def 					a__				(       snake_case__ ,				snake_case__ ,				snake_case__ ,				snake_case__ ,				snake_case__ ,				snake_case__=None       )		->      int:
			lowerCamelCase       =      []
			for epoch in range(snake_case__       ):
						# Train quickly
						model.train()
						for batch in dataloader:
									lowerCamelCase       =      batch
									lowerCamelCase       =      model(snake_case__       )
									lowerCamelCase       =      torch.nn.functional.mse_loss(snake_case__ ,				snake_case__       )
									accelerator.backward(snake_case__       )
									optimizer.step()
									optimizer.zero_grad()
						rands.append(random.random()       )  # Introduce some randomness
						if scheduler is not None:
									scheduler.step()
			return rands






class 					__magic_name__							( nn.Module       ):






				'''simple docstring'''





				def __init__( self				):





							"""simple docstring"""
							super().__init__()
							lowerCamelCase       =      nn.Parameter(torch.randn(1				)				)
							lowerCamelCase       =      nn.Parameter(torch.randn(1				)				)





				def      _lowerCAmelCase       ( self	,				_a				):





							"""simple docstring"""
							return x * self.a + self.b






class 					__magic_name__							( unittest.TestCase       ):






				'''simple docstring'''





				def      _lowerCAmelCase       ( self				):





							"""simple docstring"""




							with tempfile.TemporaryDirectory() as tmpdir:
										set_seed(42				)
										lowerCamelCase       =      DummyModel()
										lowerCamelCase       =      torch.optim.Adam(params=model.parameters()	,				lr=1e-3				)
										lowerCamelCase       =      dummy_dataloaders()
										lowerCamelCase       =      ProjectConfiguration(total_limit=1	,				project_dir=_a	,				automatic_checkpoint_naming=_a				)
										# Train baseline
										lowerCamelCase       =      Accelerator(project_config=_a				)
										lowerCamelCase       =      accelerator.prepare(
										    _a	,				_a	,				_a	,				_a				)
										# Save initial
										accelerator.save_state()

										# Save second state
										accelerator.save_state()
										self.assertEqual(len(os.listdir(accelerator.project_dir				)				)	,				1				)





				def      _lowerCAmelCase       ( self				):





							"""simple docstring"""




							with tempfile.TemporaryDirectory() as tmpdir:
										set_seed(42				)
										lowerCamelCase       =      DummyModel()
										lowerCamelCase       =      torch.optim.Adam(params=model.parameters()	,				lr=1e-3				)
										lowerCamelCase       =      dummy_dataloaders()
										# Train baseline
										lowerCamelCase       =      Accelerator()
										lowerCamelCase       =      accelerator.prepare(
										    _a	,				_a	,				_a	,				_a				)
										# Save initial
										lowerCamelCase       =      os.path.join(_a	,				"""initial"""				)
										accelerator.save_state(_a				)
										(lowerCamelCase)       =      model.a.item(), model.b.item()
										lowerCamelCase       =      optimizer.state_dict()
										lowerCamelCase       =      train(3	,				_a	,				_a	,				_a	,				_a				)
										(lowerCamelCase)       =      model.a.item(), model.b.item()
										lowerCamelCase       =      optimizer.state_dict()

										# Train partially
										set_seed(42				)
										lowerCamelCase       =      DummyModel()
										lowerCamelCase       =      torch.optim.Adam(params=model.parameters()	,				lr=1e-3				)
										lowerCamelCase       =      dummy_dataloaders()
										lowerCamelCase       =      Accelerator()
										lowerCamelCase       =      accelerator.prepare(
										    _a	,				_a	,				_a	,				_a				)
										accelerator.load_state(_a				)
										(lowerCamelCase)       =      model.a.item(), model.b.item()
										lowerCamelCase       =      optimizer.state_dict()
										self.assertEqual(_a	,				_a				)
										self.assertEqual(_a	,				_a				)
										self.assertEqual(_a	,				_a				)

										lowerCamelCase       =      train(2	,				_a	,				_a	,				_a	,				_a				)
										# Save everything
										lowerCamelCase       =      os.path.join(_a	,				"""checkpoint"""				)
										accelerator.save_state(_a				)

										# Load everything back in and make sure all states work
										accelerator.load_state(_a				)
										test_rands += train(1	,				_a	,				_a	,				_a	,				_a				)
										(lowerCamelCase)       =      model.a.item(), model.b.item()
										lowerCamelCase       =      optimizer.state_dict()
										self.assertEqual(_a	,				_a				)
										self.assertEqual(_a	,				_a				)
										self.assertEqual(_a	,				_a				)
										self.assertEqual(_a	,				_a				)





				def      _lowerCAmelCase       ( self				):





							"""simple docstring"""




							with tempfile.TemporaryDirectory() as tmpdir:
										set_seed(42				)
										lowerCamelCase       =      DummyModel()
										lowerCamelCase       =      torch.optim.Adam(params=model.parameters()	,				lr=1e-3				)
										lowerCamelCase       =      dummy_dataloaders()
										lowerCamelCase       =      ProjectConfiguration(automatic_checkpoint_naming=_a				)

										# Train baseline
										lowerCamelCase       =      Accelerator(project_dir=_a	,				project_config=_a				)
										lowerCamelCase       =      accelerator.prepare(
										    _a	,				_a	,				_a	,				_a				)
										# Save initial
										accelerator.save_state()
										(lowerCamelCase)       =      model.a.item(), model.b.item()
										lowerCamelCase       =      optimizer.state_dict()
										lowerCamelCase       =      train(3	,				_a	,				_a	,				_a	,				_a				)
										(lowerCamelCase)       =      model.a.item(), model.b.item()
										lowerCamelCase       =      optimizer.state_dict()

										# Train partially
										set_seed(42				)
										lowerCamelCase       =      DummyModel()
										lowerCamelCase       =      torch.optim.Adam(params=model.parameters()	,				lr=1e-3				)
										lowerCamelCase       =      dummy_dataloaders()
										lowerCamelCase       =      ProjectConfiguration(iteration=1	,				automatic_checkpoint_naming=_a				)
										lowerCamelCase       =      Accelerator(project_dir=_a	,				project_config=_a				)
										lowerCamelCase       =      accelerator.prepare(
										    _a	,				_a	,				_a	,				_a				)
										accelerator.load_state(os.path.join(_a	,				"""checkpoints"""	,				"""checkpoint_0"""				)				)
										(lowerCamelCase)       =      model.a.item(), model.b.item()
										lowerCamelCase       =      optimizer.state_dict()
										self.assertEqual(_a	,				_a				)
										self.assertEqual(_a	,				_a				)
										self.assertEqual(_a	,				_a				)

										lowerCamelCase       =      train(2	,				_a	,				_a	,				_a	,				_a				)
										# Save everything
										accelerator.save_state()

										# Load everything back in and make sure all states work
										accelerator.load_state(os.path.join(_a	,				"""checkpoints"""	,				"""checkpoint_1"""				)				)
										test_rands += train(1	,				_a	,				_a	,				_a	,				_a				)
										(lowerCamelCase)       =      model.a.item(), model.b.item()
										lowerCamelCase       =      optimizer.state_dict()
										self.assertEqual(_a	,				_a				)
										self.assertEqual(_a	,				_a				)
										self.assertEqual(_a	,				_a				)
										self.assertEqual(_a	,				_a				)





				def      _lowerCAmelCase       ( self				):





							"""simple docstring"""
							lowerCamelCase       =      torch.tensor([1, 2, 3]				)
							lowerCamelCase       =      torch.tensor([2, 3, 4]				)
							lowerCamelCase       =      DummyModel()
							lowerCamelCase       =      torch.optim.Adam(net.parameters()				)
							lowerCamelCase       =      Accelerator()
							with self.assertRaises(_a				) as ve:
										accelerator.register_for_checkpointing(_a	,				_a	,				_a	,				_a				)
							lowerCamelCase       =      str(ve.exception				)
							self.assertTrue("""Item at index 0""" in message				)
							self.assertTrue("""Item at index 1""" in message				)
							self.assertFalse("""Item at index 2""" in message				)
							self.assertFalse("""Item at index 3""" in message				)





				def      _lowerCAmelCase       ( self				):





							"""simple docstring"""




							with tempfile.TemporaryDirectory() as tmpdir:
										set_seed(42				)
										lowerCamelCase       =      DummyModel()
										lowerCamelCase       =      torch.optim.Adam(params=model.parameters()	,				lr=1e-3				)
										lowerCamelCase       =      torch.optim.lr_scheduler.StepLR(_a	,				step_size=1	,				gamma=0.99				)
										lowerCamelCase       =      dummy_dataloaders()
										lowerCamelCase       =      ProjectConfiguration(automatic_checkpoint_naming=_a				)
										# Train baseline
										lowerCamelCase       =      Accelerator(project_dir=_a	,				project_config=_a				)
										lowerCamelCase       =      accelerator.prepare(
										    _a	,				_a	,				_a	,				_a	,				_a				)
										# Save initial
										accelerator.save_state()
										lowerCamelCase       =      scheduler.state_dict()
										train(3	,				_a	,				_a	,				_a	,				_a	,				_a				)
										self.assertNotEqual(_a	,				scheduler.state_dict()				)

										# Load everything back in and make sure all states work
										accelerator.load_state(os.path.join(_a	,				"""checkpoints"""	,				"""checkpoint_0"""				)				)
										self.assertEqual(_a	,				scheduler.state_dict()				)





				def      _lowerCAmelCase       ( self				):





							"""simple docstring"""




							with tempfile.TemporaryDirectory() as tmpdir:
										set_seed(42				)
										lowerCamelCase       =      DummyModel()
										lowerCamelCase       =      ProjectConfiguration(automatic_checkpoint_naming=_a	,				total_limit=2				)
										# Train baseline
										lowerCamelCase       =      Accelerator(project_dir=_a	,				project_config=_a				)
										lowerCamelCase       =      accelerator.prepare(_a				)
										# Save 3 states:
										for _ in range(11				):
													accelerator.save_state()
										self.assertTrue(not os.path.exists(os.path.join(_a	,				"""checkpoints"""	,				"""checkpoint_0"""				)				)				)
										self.assertTrue(os.path.exists(os.path.join(_a	,				"""checkpoints"""	,				"""checkpoint_9"""				)				)				)
										self.assertTrue(os.path.exists(os.path.join(_a	,				"""checkpoints"""	,				"""checkpoint_10"""				)				)				)





				@require_cuda
				def      _lowerCAmelCase       ( self				):





							"""simple docstring"""
							lowerCamelCase       =      ["""torchrun""", f'--nproc_per_node={torch.cuda.device_count()}', inspect.getfile(self.__class__				)]
							execute_subprocess_async(_a	,				env=os.environ.copy()				)


if __name__ == "__main__":
					lowerCAmelCase							:    Optional[int]  							=							"""/tmp/accelerate/state_checkpointing"""
					lowerCAmelCase							:    Dict  							=							DummyModel()
					lowerCAmelCase							:    Union[str, Any]  							=							torch.optim.Adam(params=model.parameters(), lr=1e-3)
					lowerCAmelCase							:    List[Any]  							=							torch.optim.lr_scheduler.StepLR(optimizer, step_size=1, gamma=0.9_9)
					lowerCAmelCase							,		lowerCAmelCase							:    Union[str, Any]  							=							dummy_dataloaders()
					lowerCAmelCase							:    Any  							=							ProjectConfiguration(automatic_checkpoint_naming=True)
					# Train baseline
					lowerCAmelCase							:    Optional[Any]  							=							Accelerator(project_dir=savedir, project_config=project_config, mixed_precision="""no""")
					if accelerator.process_index == 0:
										if os.path.exists(savedir):
															shutil.rmtree(savedir)
										os.makedirs(savedir)
					lowerCAmelCase							,		lowerCAmelCase							,		lowerCAmelCase							,		lowerCAmelCase							,		lowerCAmelCase							:    int  							=							accelerator.prepare(
					    model, optimizer, train_dataloader, valid_dataloader, scheduler
					)
					lowerCAmelCase							,		lowerCAmelCase							:    int  							=							accelerator.prepare(model, optimizer)
					train(3, model, train_dataloader, optimizer, accelerator, scheduler)
					# Check that the intial optimizer is loaded on the GPU
					for group in optimizer.param_groups:
										lowerCAmelCase							:    int  							=							group["""params"""][0].device
										break
					assert param_device.type == accelerator.device.type
					lowerCAmelCase							:    Optional[int]  							=							model.cpu()
					accelerator.wait_for_everyone()
					accelerator.save_state()
					accelerator.wait_for_everyone()

					# Check CPU state
					accelerator.load_state(os.path.join(savedir, """checkpoints""", """checkpoint_0"""), map_location="""cpu""")
					for group in optimizer.param_groups:
										lowerCAmelCase							:    int  							=							group["""params"""][0].device
										break
					assert (
					    param_device.type == torch.device("""cpu""").type
					), F"Loaded optimizer states did not match, expected to be loaded on the CPU but got {param_device}"

					# Check device state
					model.to(accelerator.device)
					accelerator.load_state(os.path.join(savedir, """checkpoints""", """checkpoint_0"""), map_location="""on_device""")
					for group in optimizer.param_groups:
										lowerCAmelCase							:    List[str]  							=							group["""params"""][0].device
										break
					assert (
					    param_device.type == accelerator.device.type
					), F"Loaded optimizer states did not match, expected to be loaded on {accelerator.device} but got {param_device}"

					# Check error
					with pytest.raises(TypeError, match="""Unsupported optimizer map location passed"""):
										accelerator.load_state(os.path.join(savedir, """checkpoints""", """checkpoint_0"""), map_location="""invalid""")
					accelerator.wait_for_everyone()
					if accelerator.process_index == 0:
										shutil.rmtree(savedir)
					accelerator.wait_for_everyone()









"""simple docstring"""




def 					a__				(       snake_case__ = 1_00_00_00       )		->      int:
			lowerCamelCase       =      1
			lowerCamelCase       =      1
			lowerCamelCase       =      {1: 1}

			for inputa in range(2 ,				snake_case__       ):
						lowerCamelCase       =      0
						lowerCamelCase       =      inputa

						while True:
									if number in counters:
												counter += counters[number]
												break
									if number % 2 == 0:
												number //= 2
												counter += 1
									else:
												lowerCamelCase       =      (3 * number) + 1
												counter += 1

						if inputa not in counters:
									lowerCamelCase       =      counter

						if counter > pre_counter:
									lowerCamelCase       =      inputa
									lowerCamelCase       =      counter
			return largest_number


if __name__ == "__main__":
					print(solution(int(input().strip())))



