import math






def    UpperCAmelCase__(						lowerCamelCase_  ):



			"""simple docstring"""





			if n <= 0:
						raise ValueError("Only positive integers have prime factors"  )
			_snake_case              =      []
			while n % 2 == 0:
						pf.append(2  )
						_snake_case              =      int(n / 2  )
			for i in range(3							,	int(math.sqrt(lowerCamelCase_  )  ) + 1							,	2  ):
						while n % i == 0:
									pf.append(lowerCamelCase_  )
									_snake_case              =      int(n / i  )
			if n > 2:
						pf.append(lowerCamelCase_  )
			return pf






def    UpperCAmelCase__(						lowerCamelCase_  ):



			"""simple docstring"""





			if n <= 0:
						raise ValueError("Only positive numbers are accepted"  )
			_snake_case              =      1
			_snake_case              =      1
			while n % 2 == 0:
						temp += 1
						_snake_case              =      int(n / 2  )
			div *= temp
			for i in range(3							,	int(math.sqrt(lowerCamelCase_  )  ) + 1							,	2  ):
						_snake_case              =      1
						while n % i == 0:
									temp += 1
									_snake_case              =      int(n / i  )
						div *= temp
			if n > 1:
						div *= 2
			return div






def    UpperCAmelCase__(						lowerCamelCase_  ):



			"""simple docstring"""





			if n <= 0:
						raise ValueError("Only positive numbers are accepted"  )
			_snake_case              =      1
			_snake_case              =      1
			while n % 2 == 0:
						temp += 1
						_snake_case              =      int(n / 2  )
			if temp > 1:
						s *= (2**temp - 1) / (2 - 1)
			for i in range(3							,	int(math.sqrt(lowerCamelCase_  )  ) + 1							,	2  ):
						_snake_case              =      1
						while n % i == 0:
									temp += 1
									_snake_case              =      int(n / i  )
						if temp > 1:
									s *= (i**temp - 1) / (i - 1)
			return int(lowerCamelCase_  )






def    UpperCAmelCase__(						lowerCamelCase_  ):



			"""simple docstring"""





			_snake_case              =      n
			for x in set(prime_factors(lowerCamelCase_  )  ):
						s *= (x - 1) / x
			return int(lowerCamelCase_  )


if __name__ == "__main__":
			import doctest

			doctest.testmod()


def    UpperCAmelCase__(						lowerCamelCase_							,	lowerCamelCase_  ):



			"""simple docstring"""





			_snake_case              =      sorted(lowerCamelCase_							,	key=lambda lowerCamelCase_  : value[2]							,	reverse=lowerCamelCase_  )

			# Create a list of size equal to the maximum deadline
			# and initialize it with -1
			_snake_case              =      max(lowerCamelCase_							,	key=lambda lowerCamelCase_  : value[1]  )[1]
			_snake_case              =      [-1] * max_deadline

			# Finding the maximum profit and the count of jobs
			_snake_case              =      0
			_snake_case              =      0
			for job in jobs:
						# Find a free time slot for this job
						# (Note that we start from the last possible slot)
						for i in range(job[1] - 1							,	-1							,	-1  ):
									if time_slots[i] == -1:
												_snake_case              =      job[0]
												count += 1
												max_profit += job[2]
												break
			return [count, max_profit]


if __name__ == "__main__":
			import doctest

			doctest.testmod()

