




'''simple docstring'''

a       :						Dict								=		range(2, 20 + 1)
a       :						Optional[int]								=		[10**k for k in range(ks[-1] + 1)]
a       :						dict[int, dict[int, list[list[int]]]]								=		{}


def __UpperCAmelCase	(   _UpperCAmelCase		:   Union[str, Any]		,				_UpperCAmelCase		:   Dict		,				_UpperCAmelCase		:   Optional[Any]		,				_UpperCAmelCase		:   Optional[Any]						)      ->      int:
			__snake_case			=		sum(a_i[j] for j in range(_UpperCAmelCase		,				len(_UpperCAmelCase						)						)						)
			__snake_case			=		sum(a_i[j] * base[j] for j in range(min(len(_UpperCAmelCase						)		,				_UpperCAmelCase						)						)						)

			__snake_case		,     __snake_case			=		0, 0
			__snake_case			=		n - i

			__snake_case			=		memo.get(_UpperCAmelCase						)

			if sub_memo is not None:
						__snake_case			=		sub_memo.get(_UpperCAmelCase						)

						if jumps is not None and len(_UpperCAmelCase						) > 0:
									# find and make the largest jump without going over
									__snake_case			=		-1
									for _k in range(len(_UpperCAmelCase						) - 1		,				-1		,				-1						):
												if jumps[_k][2] <= k and jumps[_k][1] <= max_dn:
															__snake_case			=		_k
															break

									if max_jump >= 0:
												__snake_case		,     __snake_case		,     __snake_case			=		jumps[max_jump]
												# since the difference between jumps is cached, add c
												__snake_case			=		diff + c
												for j in range(min(_UpperCAmelCase		,				len(_UpperCAmelCase						)						)						):
															__snake_case		,     __snake_case			=		divmod(_UpperCAmelCase		,				10						)
												if new_c > 0:
															add(_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase						)

						else:
									__snake_case			=		[]
			else:
						__snake_case			=		{c: []}
						__snake_case			=		sub_memo

			if dn >= max_dn or c + diff >= base[k]:
						return diff, dn

			if k > ks[0]:
						while True:
									# keep doing smaller jumps
									__snake_case		,     __snake_case			=		next_term(_UpperCAmelCase		,				k - 1		,				i + dn		,				_UpperCAmelCase						)
									diff += _diff
									dn += terms_jumped

									if dn >= max_dn or c + diff >= base[k]:
												break
			else:
						# would be too small a jump, just compute sequential terms instead
						__snake_case		,     __snake_case			=		compute(_UpperCAmelCase		,				_UpperCAmelCase		,				i + dn		,				_UpperCAmelCase						)
						diff += _diff
						dn += terms_jumped

			__snake_case			=		sub_memo[c]

			# keep jumps sorted by # of terms skipped
			__snake_case			=		0
			while j < len(_UpperCAmelCase						):
						if jumps[j][1] > dn:
									break
						j += 1

			# cache the jump for this value digitsum(b) and c
			sub_memo[c].insert(_UpperCAmelCase		,				(diff, dn, k)						)
			return (diff, dn)


def __UpperCAmelCase	(   _UpperCAmelCase		:   Union[str, Any]		,				_UpperCAmelCase		:   Union[str, Any]		,				_UpperCAmelCase		:   Optional[Any]		,				_UpperCAmelCase		:   Optional[int]						)      ->      Optional[int]:
			if i >= n:
						return 0, i
			if k > len(_UpperCAmelCase						):
						a_i.extend([0 for _ in range(k - len(_UpperCAmelCase						)						)]						)

			# note: a_i -> b * 10^k + c
			# ds_b -> digitsum(b)
			# ds_c -> digitsum(c)
			__snake_case			=		i
			__snake_case		,     __snake_case		,     __snake_case			=		0, 0, 0
			for j in range(len(_UpperCAmelCase						)						):
						if j >= k:
									ds_b += a_i[j]
						else:
									ds_c += a_i[j]

			while i < n:
						i += 1
						__snake_case			=		ds_c + ds_b
						diff += addend
						__snake_case			=		0
						for j in range(_UpperCAmelCase						):
									__snake_case			=		a_i[j] + addend
									__snake_case		,     __snake_case			=		divmod(_UpperCAmelCase		,				10						)

									ds_c += a_i[j]

						if addend > 0:
									break

			if addend > 0:
						add(_UpperCAmelCase		,				_UpperCAmelCase		,				_UpperCAmelCase						)
			return diff, i - start_i


def __UpperCAmelCase	(   _UpperCAmelCase		:   Union[str, Any]		,				_UpperCAmelCase		:   Tuple		,				_UpperCAmelCase		:   str						)      ->      Tuple:
			for j in range(_UpperCAmelCase		,				len(_UpperCAmelCase						)						):
						__snake_case			=		digits[j] + addend
						if s >= 10:
									__snake_case		,     __snake_case			=		divmod(_UpperCAmelCase		,				10						)
									__snake_case			=		addend // 10 + quotient
						else:
									__snake_case			=		s
									__snake_case			=		addend // 10

						if addend == 0:
									break

			while addend > 0:
						__snake_case		,     __snake_case			=		divmod(_UpperCAmelCase		,				10						)
						digits.append(_UpperCAmelCase						)


def __UpperCAmelCase	(   _UpperCAmelCase		:   int = 10**15						)      ->      int:
			__snake_case			=		[1]
			__snake_case			=		1
			__snake_case			=		0
			while True:
						__snake_case		,     __snake_case			=		next_term(_UpperCAmelCase		,				20		,				i + dn		,				_UpperCAmelCase						)
						dn += terms_jumped
						if dn == n - i:
									break

			__snake_case			=		0
			for j in range(len(_UpperCAmelCase						)						):
						a_n += digits[j] * 10**j
			return a_n


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







"""simple docstring"""






def      lowerCAmelCase__			(		__magic_name__      )						->int:

			if not isinstance(__magic_name__			,   __magic_name__      ):
						raise ValueError("multiplicative_persistence() only accepts integral values"      )
			if num < 0:
						raise ValueError("multiplicative_persistence() does not accept negative values"      )

			__lowercase       =       0
			__lowercase       =       str(__magic_name__      )

			while len(__magic_name__      ) != 1:
						__lowercase       =       [int(__magic_name__      ) for i in num_string]

						__lowercase       =       1
						for i in range(0			,   len(__magic_name__      )      ):
									total *= numbers[i]

						__lowercase       =       str(__magic_name__      )

						steps += 1
			return steps



def      lowerCAmelCase__			(		__magic_name__      )						->int:

			if not isinstance(__magic_name__			,   __magic_name__      ):
						raise ValueError("additive_persistence() only accepts integral values"      )
			if num < 0:
						raise ValueError("additive_persistence() does not accept negative values"      )

			__lowercase       =       0
			__lowercase       =       str(__magic_name__      )

			while len(__magic_name__      ) != 1:
						__lowercase       =       [int(__magic_name__      ) for i in num_string]

						__lowercase       =       0
						for i in range(0			,   len(__magic_name__      )      ):
									total += numbers[i]

						__lowercase       =       str(__magic_name__      )

						steps += 1
			return steps


if __name__ == "__main__":
					import doctest

					doctest.testmod()





