

from __future__ import annotations

def     a__  (	UpperCAmelCase							:    int       ,				UpperCAmelCase							:    int       ,				UpperCAmelCase							:    int    )						->		int:
  assert n > 1 and a > 0 and greatest_common_divisor(UpperCAmelCase       ,				UpperCAmelCase    ) == 1
  (UpperCAmelCase) :							Union[str, Any]								=				extended_gcd(UpperCAmelCase       ,				UpperCAmelCase    )  # Implemented below
  UpperCAmelCase :							str								=				(b * s) % n
  return x

def     a__  (	UpperCAmelCase							:    int       ,				UpperCAmelCase							:    int    )						->		int:
  (UpperCAmelCase) :							int								=				extended_euclid(UpperCAmelCase       ,				UpperCAmelCase    )  # Implemented below
  if b < 0:
    UpperCAmelCase :							List[Any]								=				(b % n + n) % n
  return b

def     a__  (	UpperCAmelCase							:    int       ,				UpperCAmelCase							:    int       ,				UpperCAmelCase							:    int    )						->		int:
  UpperCAmelCase :							Union[str, Any]								=				invert_modulo(UpperCAmelCase       ,				UpperCAmelCase    )
  UpperCAmelCase :							List[str]								=				(b * s) % n
  return x

def     a__  (	UpperCAmelCase							:    int       ,				UpperCAmelCase							:    int    )						->		tuple[int, int, int]:
  assert a >= 0 and b >= 0

  if b == 0:
    UpperCAmelCase :							int								=				a, 1, 0
  else:
    (UpperCAmelCase) :							List[Any]								=				extended_gcd(UpperCAmelCase       ,				a % b    )
    UpperCAmelCase :							Optional[Any]								=				q
    UpperCAmelCase :							int								=				p - q * (a // b)

  assert a % d == 0 and b % d == 0
  assert d == a * x + b * y

  return (d, x, y)

def     a__  (	UpperCAmelCase							:    int       ,				UpperCAmelCase							:    int    )						->		tuple[int, int]:
  if b == 0:
    return (1, 0)
  (UpperCAmelCase) :							Any								=				extended_euclid(UpperCAmelCase       ,				a % b    )
  UpperCAmelCase :							Dict								=				a // b
  return (y, x - k * y)

def     a__  (	UpperCAmelCase							:    int       ,				UpperCAmelCase							:    int    )						->		int:
  if a < b:
    UpperCAmelCase :							List[Any]								=				b, a

  while a % b != 0:
    UpperCAmelCase :							Tuple								=				b, a % b

  return b


if __name__ == "__main__":
     from doctest import testmod

     testmod(name="modular_division", verbose=True)
     testmod(name="modular_division2", verbose=True)
     testmod(name="invert_modulo", verbose=True)
     testmod(name="extended_gcd", verbose=True)
     testmod(name="extended_euclid", verbose=True)
     testmod(name="greatest_common_divisor", verbose=True)








import decimal

def     a__  (	)						->		int:
  UpperCAmelCase :							List[Any]								=				0
  UpperCAmelCase :							Dict								=				decimal.Context(prec=105    )
  for i in range(2       ,				100    ):
    UpperCAmelCase :							List[str]								=				decimal.Decimal(UpperCAmelCase    )
    UpperCAmelCase :							List[str]								=				number.sqrt(UpperCAmelCase    )
    if len(str(UpperCAmelCase    )    ) > 1:
      answer += int(str(UpperCAmelCase    )[0]    )
      UpperCAmelCase :							str								=				str(UpperCAmelCase    )[2:101]
      answer += sum(int(UpperCAmelCase    ) for x in sqrt_number_str    )
  return answer


if __name__ == "__main__":
     import doctest

     doctest.testmod()
     print(f"""{solution() = }""")





