'''
# Sample code to perform I/O:
 
name = input()                  # Reading input from STDIN
print('Hi, %s.' % name)         # Writing output to STDOUT
 
# Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
'''
 
# Write your code here
 
test_cases = int(input()) 
count = 0
string_length = 0
string = ''
magic_word = ''
magic_letters = [67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113]
 
def nearest_prime(num):
  
  smallest_difference = 1000
  nearest_prime = 0
 
  for letter in magic_letters:
    difference = abs(num - letter)
    
    if difference < smallest_difference:
      smallest_difference = difference
      nearest_prime = letter
 
  return nearest_prime
 
while(count < test_cases):
  string_length = int(input())
  string = input()
  count += 1
 
  for x in string:
    magic_word += chr(nearest_prime(ord(x)))
 
  print(magic_word)
  magic_word = ''