



__snake_case            =   range(2, 20 + 1)
__snake_case            =   [10**k for k in range(ks[-1] + 1)]
__snake_case            =   {}






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		Any       ,  SCREAMING_SNAKE_CASE_   :		List[Any]       ,  SCREAMING_SNAKE_CASE_   :		List[str]       ,  SCREAMING_SNAKE_CASE_   :		int	):





			"""simple docstring"""




			UpperCamelCase         =					sum(a_i[j] for j in range(SCREAMING_SNAKE_CASE_       ,  len(SCREAMING_SNAKE_CASE_	)	)	)
			UpperCamelCase         =					sum(a_i[j] * base[j] for j in range(min(len(SCREAMING_SNAKE_CASE_	)       ,  SCREAMING_SNAKE_CASE_	)	)	)

			UpperCamelCase  ,  UpperCamelCase         =					0, 0
			UpperCamelCase         =					n - i

			UpperCamelCase         =					memo.get(SCREAMING_SNAKE_CASE_	)

			if sub_memo is not None:
						UpperCamelCase         =					sub_memo.get(SCREAMING_SNAKE_CASE_	)

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

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

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

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

			if k > ks[0]:
						while True:
									# keep doing smaller jumps
									UpperCamelCase  ,  UpperCamelCase         =					next_term(SCREAMING_SNAKE_CASE_       ,  k - 1       ,  i + dn       ,  SCREAMING_SNAKE_CASE_	)
									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
						UpperCamelCase  ,  UpperCamelCase         =					compute(SCREAMING_SNAKE_CASE_       ,  SCREAMING_SNAKE_CASE_       ,  i + dn       ,  SCREAMING_SNAKE_CASE_	)
						diff += _diff
						dn += terms_jumped

			UpperCamelCase         =					sub_memo[c]

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

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






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		List[str]       ,  SCREAMING_SNAKE_CASE_   :		Optional[Any]       ,  SCREAMING_SNAKE_CASE_   :		int       ,  SCREAMING_SNAKE_CASE_   :		Optional[int]	):





			"""simple docstring"""




			if i >= n:
						return 0, i
			if k > len(SCREAMING_SNAKE_CASE_	):
						a_i.extend([0 for _ in range(k - len(SCREAMING_SNAKE_CASE_	)	)]	)

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

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

									ds_c += a_i[j]

						if addend > 0:
									break

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






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		Tuple       ,  SCREAMING_SNAKE_CASE_   :		Any       ,  SCREAMING_SNAKE_CASE_   :		Dict	):





			"""simple docstring"""




			for j in range(SCREAMING_SNAKE_CASE_       ,  len(SCREAMING_SNAKE_CASE_	)	):
						UpperCamelCase         =					digits[j] + addend
						if s >= 10:
									UpperCamelCase  ,  UpperCamelCase         =					divmod(SCREAMING_SNAKE_CASE_       ,  10	)
									UpperCamelCase         =					addend // 10 + quotient
						else:
									UpperCamelCase         =					s
									UpperCamelCase         =					addend // 10

						if addend == 0:
									break

			while addend > 0:
						UpperCamelCase  ,  UpperCamelCase         =					divmod(SCREAMING_SNAKE_CASE_       ,  10	)
						digits.append(SCREAMING_SNAKE_CASE_	)






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		int = 10**15	):





			"""simple docstring"""




			UpperCamelCase         =					[1]
			UpperCamelCase         =					1
			UpperCamelCase         =					0
			while True:
						UpperCamelCase  ,  UpperCamelCase         =					next_term(SCREAMING_SNAKE_CASE_       ,  20       ,  i + dn       ,  SCREAMING_SNAKE_CASE_	)
						dn += terms_jumped
						if dn == n - i:
									break

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


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








import qiskit






def 							_lowercase    (		SCREAMING_SNAKE_CASE_   :		int = 2	):





			"""simple docstring"""




			UpperCamelCase         =					qubits

			# Using Aer's simulator
			UpperCamelCase         =					qiskit.Aer.get_backend("""aer_simulator"""	)

			# Creating a Quantum Circuit acting on the q register
			UpperCamelCase         =					qiskit.QuantumCircuit(SCREAMING_SNAKE_CASE_       ,  SCREAMING_SNAKE_CASE_	)

			# Adding a H gate on qubit 0 (now q0 in superposition)
			circuit.h(0	)

			for i in range(1       ,  SCREAMING_SNAKE_CASE_	):
						# Adding CX (CNOT) gate
						circuit.cx(i - 1       ,  SCREAMING_SNAKE_CASE_	)

			# Mapping the quantum measurement to the classical bits
			circuit.measure(list(range(SCREAMING_SNAKE_CASE_	)	)       ,  list(range(SCREAMING_SNAKE_CASE_	)	)	)

			# Now measuring any one qubit would affect other qubits to collapse
			# their super position and have same state as the measured one.

			# Executing the circuit on the simulator
			UpperCamelCase         =					qiskit.execute(SCREAMING_SNAKE_CASE_       ,  SCREAMING_SNAKE_CASE_       ,  shots=1_000	)

			return job.result().get_counts(SCREAMING_SNAKE_CASE_	)


if __name__ == "__main__":
			print(F'''Total count for various states are: {quantum_entanglement(3)}''')




