def    UpperCAmelCase__(						lowerCamelCase_  ):



			"""simple docstring"""





			_snake_case              =      len(lowerCamelCase_  )

			# Set the gap value to be decreased by a factor of 1.3
			# after each iteration
			_snake_case              =      1.3

			# Continue sorting until the gap is 1
			while gap > 1:
						# Decrease the gap value
						_snake_case              =      int(gap / shrink  )

						# Sort the elements using insertion sort
						for i in range(lowerCamelCase_							,	len(lowerCamelCase_  )  ):
									_snake_case              =      collection[i]
									_snake_case              =      i
									while j >= gap and collection[j - gap] > temp:
												_snake_case              =      collection[j - gap]
												j -= gap
									_snake_case              =      temp

			return collection


if __name__ == "__main__":
			import doctest

			doctest.testmod()


from math import gcd






def    UpperCAmelCase__(						lowerCamelCase_ = 12000  ):



			"""simple docstring"""





			_snake_case              =      0
			for d in range(max_d + 1  ):
						for n in range(d // 3 + 1							,	(d + 1) // 2  ):
									if gcd(lowerCamelCase_							,	lowerCamelCase_  ) == 1:
												fractions_number += 1
			return fractions_number


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

