



from __future__ import annotations

def       A_   (						__a  :					int			,		__a  :					int			,		__a  :					int		):

				"""simple docstring"""
				assert n > 1 and a > 0 and greatest_common_divisor(__a			,		__a		) == 1
				((a__)   ,      (a__)   ,      (a__))					   =		extended_gcd(__a			,		__a		)  # Implemented below
				a__					   =		(b * s) % n
				return x

def       A_   (						__a  :					int			,		__a  :					int		):

				"""simple docstring"""
				((a__)   ,      (a__))					   =		extended_euclid(__a			,		__a		)  # Implemented below
				if b < 0:
								a__					   =		(b % n + n) % n
				return b

def       A_   (						__a  :					int			,		__a  :					int			,		__a  :					int		):

				"""simple docstring"""
				a__					   =		invert_modulo(__a			,		__a		)
				a__					   =		(b * s) % n
				return x

def       A_   (						__a  :					int			,		__a  :					int		):

				"""simple docstring"""
				assert a >= 0 and b >= 0

				if b == 0:
								a__   ,      a__   ,      a__					   =		a, 1, 0
				else:
								((a__)   ,      (a__)   ,      (a__))					   =		extended_gcd(__a			,		a % b		)
								a__					   =		q
								a__					   =		p - q * (a // b)

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

				return (d, x, y)

def       A_   (						__a  :					int			,		__a  :					int		):

				"""simple docstring"""
				if b == 0:
								return (1, 0)
				((a__)   ,      (a__))					   =		extended_euclid(__a			,		a % b		)
				a__					   =		a // b
				return (y, x - k * y)

def       A_   (						__a  :					int			,		__a  :					int		):

				"""simple docstring"""
				if a < b:
								a__   ,      a__					   =		b, a

				while a % b != 0:
								a__   ,      a__					   =		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)






from math import gcd

def       A_   (						__a  :					int = 12_000		):

				"""simple docstring"""
				a__					   =		0
				for d in range(max_d + 1		):
								for n in range(d // 3 + 1			,		(d + 1) // 2		):
												if gcd(__a			,		__a		) == 1:
																fractions_number += 1
				return fractions_number


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

