





'''simple docstring'''


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







def    _lowerCamelCase  (__lowerCamelCase  :     Dict					,  __lowerCamelCase  :     List[str]					,  __lowerCamelCase  :     Any					,  __lowerCamelCase  :     int     )   ->    Tuple:
			a__     = sum(a_i[j] for j in range(__lowerCamelCase					,  len(__lowerCamelCase     )     )     )
			a__     = sum(a_i[j] * base[j] for j in range(min(len(__lowerCamelCase     )					,  __lowerCamelCase     )     )     )

			a__   ,				a__     = 0, 0
			a__     = n - i

			a__     = memo.get(__lowerCamelCase     )

			if sub_memo is not None:
						a__     = sub_memo.get(__lowerCamelCase     )

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

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

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

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

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

			a__     = sub_memo[c]

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

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







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

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

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

									ds_c += a_i[j]

						if addend > 0:
									break

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







def    _lowerCamelCase  (__lowerCamelCase  :     Any					,  __lowerCamelCase  :     Dict					,  __lowerCamelCase  :     Any     )   ->    List[Any]:
			for j in range(__lowerCamelCase					,  len(__lowerCamelCase     )     ):
						a__     = digits[j] + addend
						if s >= 10:
									a__   ,				a__     = divmod(__lowerCamelCase					,  10     )
									a__     = addend // 10 + quotient
						else:
									a__     = s
									a__     = addend // 10

						if addend == 0:
									break

			while addend > 0:
						a__   ,				a__     = divmod(__lowerCamelCase					,  10     )
						digits.append(__lowerCamelCase     )







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

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


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










'''simple docstring'''


import importlib
import os
import sys


# This is required to make the module import works (when the python process is running from the root of the repo)
sys.path.append(".")







def    _lowerCamelCase  (__lowerCamelCase  :     List[str]     )   ->    List[str]:
			a__     = test_file.split(os.path.sep     )
			if components[0:2] != ["tests", "models"]:
						raise ValueError(
						    "`test_file` should start with `tests/models/` (with `/` being the OS specific path separator). Got "
						    f'''{test_file} instead.'''     )
			a__     = components[-1]
			if not test_fn.endswith("py"     ):
						raise ValueError(f'''`test_file` should be a python file. Got {test_fn} instead.'''     )
			if not test_fn.startswith("test_modeling_"     ):
						raise ValueError(
						    f'''`test_file` should point to a file name of the form `test_modeling_*.py`. Got {test_fn} instead.'''     )

			a__     = components[:-1] + [test_fn.replace(".py"					,  ""     )]
			a__     = ".".join(__lowerCamelCase     )

			return test_module_path







def    _lowerCamelCase  (__lowerCamelCase  :     Union[str, Any]     )   ->    Optional[Any]:
			a__     = get_module_path(__lowerCamelCase     )
			a__     = importlib.import_module(__lowerCamelCase     )

			return test_module







def    _lowerCamelCase  (__lowerCamelCase  :     Optional[int]     )   ->    Union[str, Any]:
			a__     = []
			a__     = get_test_module(__lowerCamelCase     )
			for attr in dir(__lowerCamelCase     ):
						if attr.endswith("ModelTester"     ):
									tester_classes.append(getattr(__lowerCamelCase					,  __lowerCamelCase     )     )

    # sort with class names
			return sorted(__lowerCamelCase					,  key=lambda __lowerCamelCase     : x.__name__     )







def    _lowerCamelCase  (__lowerCamelCase  :     Tuple     )   ->    Tuple:
			a__     = []
			a__     = get_test_module(__lowerCamelCase     )
			for attr in dir(__lowerCamelCase     ):
						a__     = getattr(__lowerCamelCase					,  __lowerCamelCase     )
						# (TF/Flax)ModelTesterMixin is also an attribute in specific model test module. Let's exclude them by checking
						# `all_model_classes` is not empty (which also excludes other special classes).
						a__     = getattr(__lowerCamelCase					,  "all_model_classes"					,  []     )
						if len(__lowerCamelCase     ) > 0:
									test_classes.append(__lowerCamelCase     )

    # sort with class names
			return sorted(__lowerCamelCase					,  key=lambda __lowerCamelCase     : x.__name__     )







def    _lowerCamelCase  (__lowerCamelCase  :     List[Any]     )   ->    List[Any]:
			a__     = get_test_classes(__lowerCamelCase     )
			a__     = set()
			for test_class in test_classes:
						model_classes.update(test_class.all_model_classes     )

			# sort with class names
			return sorted(__lowerCamelCase					,  key=lambda __lowerCamelCase     : x.__name__     )







def    _lowerCamelCase  (__lowerCamelCase  :     str     )   ->    Dict:
			a__     = test_class()
			if hasattr(__lowerCamelCase					,  "setUp"     ):
						test.setUp()

			a__     = None
			if hasattr(__lowerCamelCase					,  "model_tester"     ):
						# `(TF/Flax)ModelTesterMixin` has this attribute default to `None`. Let's skip this case.
						if test.model_tester is not None:
									a__     = test.model_tester.__class__

			return model_tester







def    _lowerCamelCase  (__lowerCamelCase  :     Dict					,  __lowerCamelCase  :     Optional[int]     )   ->    List[Any]:
			a__     = get_test_classes(__lowerCamelCase     )

			a__     = []
			for test_class in test_classes:
						if model_class in test_class.all_model_classes:
									target_test_classes.append(__lowerCamelCase     )

    # sort with class names
			return sorted(__lowerCamelCase					,  key=lambda __lowerCamelCase     : x.__name__     )







def    _lowerCamelCase  (__lowerCamelCase  :     Any					,  __lowerCamelCase  :     Tuple     )   ->    Dict:
			a__     = get_test_classes_for_model(__lowerCamelCase					,  __lowerCamelCase     )

			a__     = []
			for test_class in test_classes:
						a__     = get_model_tester_from_test_class(__lowerCamelCase     )
						if tester_class is not None:
									tester_classes.append(__lowerCamelCase     )

    # sort with class names
			return sorted(__lowerCamelCase					,  key=lambda __lowerCamelCase     : x.__name__     )







def    _lowerCamelCase  (__lowerCamelCase  :     List[str]     )   ->    int:
			a__     = get_test_classes(__lowerCamelCase     )
			a__     = {test_class: get_model_tester_from_test_class(__lowerCamelCase     ) for test_class in test_classes}
			return test_tester_mapping







def    _lowerCamelCase  (__lowerCamelCase  :     Any     )   ->    List[Any]:
			a__     = get_model_classes(__lowerCamelCase     )
			a__     = {
			    model_class: get_test_classes_for_model(__lowerCamelCase					,  __lowerCamelCase     ) for model_class in model_classes
			}
			return model_test_mapping







def    _lowerCamelCase  (__lowerCamelCase  :     Tuple     )   ->    Tuple:
			a__     = get_model_classes(__lowerCamelCase     )
			a__     = {
			    model_class: get_tester_classes_for_model(__lowerCamelCase					,  __lowerCamelCase     ) for model_class in model_classes
			}
			return model_to_tester_mapping







def    _lowerCamelCase  (__lowerCamelCase  :     str     )   ->    Dict:
			if isinstance(__lowerCamelCase					,  __lowerCamelCase     ):
						return o
			elif isinstance(__lowerCamelCase					,  __lowerCamelCase     ):
						return o.__name__
			elif isinstance(__lowerCamelCase					,  (list, tuple)     ):
						return [to_json(__lowerCamelCase     ) for x in o]
			elif isinstance(__lowerCamelCase					,  __lowerCamelCase     ):
						return {to_json(__lowerCamelCase     ): to_json(__lowerCamelCase     ) for k, v in o.items()}
			else:
						return o



