from math import ceil, sqrt


def is_indivisible_by(nr, primes):
	# Ckeck whether nr is prime, but only using pre-computed list of factors
	for check_prime in primes:
		if nr % check_prime != 0:
			return False
	return True


def count_factors(N, primes, max_known):
	fac_cnt = 0
	# Check if the number is divisible by prime factors
	for check_prime in primes:
		remainder = N
		# Check if N is divisible by p multiple times
		while remainder % check_prime == 0:
			remainder //= check_prime
			fac_cnt += 1
			if fac_cnt > 2:
				return 3
		if remainder < N and remainder != 1:
			# Check whether the 'complement' of factor p is a prime
			if is_indivisible_by(remainder, primes):
				# Complement not prime, so 3+ factors (1 for remainder and 2 for complement)
				return 3
			elif remainder > max_known:
				# Prime that's higher than what we check, so add a factor
				fac_cnt += 1
				if fac_cnt > 2:
					return 3
	return fac_cnt


def expand_primes(primes, highest, upto):
	# Find more primes if we don't have enough yet
	for new_prime in range(highest, upto + 1):
		highest += 1
		for check_prime in primes:
			if highest % check_prime == 0:
				break
		else:
			primes.append(highest)
	return highest, primes


def do_for_Ns(Ns):
	# Solve for several Ns, doing Ns from low to high to need minimal prime factors
	results = {}
	primes = []
	max_known = 1
	for N in sorted(Ns):
		# Expand primes if we don't know enough
		# Note that the sqrt trick brings is down from 2m46s to 0m0.03s
		max_known, primes = expand_primes(primes, highest=max_known, upto=int(ceil(sqrt(N))))
		# Find the number of prime factors, cutting out at 2
		fac_cnt = count_factors(N, primes, max_known)
		results[N] = fac_cnt
	for N in Ns:
		print('{0:3d} ~  {1:d} {2:s}'.format(N, results[N], '**' if results[N] == 2 else ''))


# do_for_Ns(range(1, 31))
do_for_Ns([919 * 919, 919 * 929, 863 * 1217, 3 * 73823,
    113 * 103 * 101, 103 * 103 * 103, 2 * 2 * 73823, int(2**20)])