def primeString(s):
	def getPrimeString(n):
		if n<65 or 91<=n<=96 or n>122:
			return ord(" ")
		if n in nearestPrime:
			return nearestPrime[n]
		if checkPrime(n):
			nearestPrime[n] = n
			return n
		i = 1
		if 65<=n<=90:
			limits = (65, 90)
		else:
			limits = (97, 122)
		while i<26:
			if limits[0]<=n-i<=limits[1] and checkPrime(n-i):
				nearestPrime[n] = n-i
				return n-i
			if limits[0]<=n+i<=limits[1] and checkPrime(n+i):
				nearestPrime[n] = n+i
				return n+i
			i += 1

	def checkPrime(n):
		if n in isPrime:
			return isPrime[n]
		for i in range(2, int(n**0.5)+1):
			if n%i==0:
				isPrime[n] = False
				return False
		isPrime[n] = True
		return True

	isPrime, nearestPrime = {}, {}
	res = ""
	for i in s:
		res += chr(getPrimeString(ord(i)))
	return res