'''
# 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 = ''