<?php
 
 
function isPrime($num) {
    //1 is not prime. See: http://e...content-available-to-author-only...a.org/wiki/Prime_number#Primality_of_one
    if($num == 1)
        return false;
 
    //2 is prime (the only even number that is prime)
    if($num == 2)
        return true;
 
    /**
     * if the number is divisible by two, then it's not prime and it's no longer
     * needed to check other even numbers
     */
    if($num % 2 == 0) {
        return false;
    }
 
    /**
     * Checks the odd numbers. If any of them is a factor, then it returns false.
     * The sqrt can be an aproximation, hence just for the sake of
     * security, one rounds it to the next highest integer value.
     */
    $ceil = ceil(sqrt($num));
    for($i = 3; $i <= $ceil; $i = $i + 2) {
        if($num % $i == 0)
            return false;
    }
 
    return true;
}
 
$inputs=array();
while($f=fgets(STDIN))
{
	array_push($inputs,$f);
}
 
$num_tests=$inputs[0];
if($num_tests<=100)
{
	for($i=0;$i<$num_tests;$i++)
	{
		$strlen=$inputs[$i*2+1];
		$str=$inputs[$i*2+2];
		if($strlen>=1 && $strlen<=500)
		{
			$str_arr=str_split($str);
			$arr_ascii=array_map(function($val){
				return ord($val);
				},$str_arr);
			$arr_updated=array_map(function($val){
			    $main_prime=$val;
			    if((($val>=65 && $val<=90)||($val>=97 && $val<=122)) && !isPrime($val))
			    {
			        $truth=false;
			        $i=1;
			        while(!$truth){
			            $updated_one=$val+$i;
			            $truth=isPrime($updated_one);
			            ++$i;
			        }
 
			        $nxt_prime=$updated_one;//127
			        //$may_pre_prime=$val-($nxt_prime-$val);//115
			        for($k=65;$k<$val;$k++)
			        {
			            if(isPrime($k) && ($nxt_prime-$val >= $val-$k || $nxt_prime > ord('z')))
			                $main_prime=$k;
			        }
 
			        if($main_prime==$val)
			            $main_prime=$nxt_prime;
			    }
			    else if($main_prime!=10 && ($main_prime<65 || $main_prime>122 )
			        $main_prime=67;
			    return chr($main_prime);
			},$arr_ascii);
			echo implode("",$arr_updated)."\n";
		}
 
	}
 
}
 
 
?>
 

PD9waHAKCgpmdW5jdGlvbiBpc1ByaW1lKCRudW0pIHsKICAgIC8vMSBpcyBub3QgcHJpbWUuIFNlZTogaHR0cDovL2UuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmEub3JnL3dpa2kvUHJpbWVfbnVtYmVyI1ByaW1hbGl0eV9vZl9vbmUKICAgIGlmKCRudW0gPT0gMSkKICAgICAgICByZXR1cm4gZmFsc2U7CgogICAgLy8yIGlzIHByaW1lICh0aGUgb25seSBldmVuIG51bWJlciB0aGF0IGlzIHByaW1lKQogICAgaWYoJG51bSA9PSAyKQogICAgICAgIHJldHVybiB0cnVlOwoKICAgIC8qKgogICAgICogaWYgdGhlIG51bWJlciBpcyBkaXZpc2libGUgYnkgdHdvLCB0aGVuIGl0J3Mgbm90IHByaW1lIGFuZCBpdCdzIG5vIGxvbmdlcgogICAgICogbmVlZGVkIHRvIGNoZWNrIG90aGVyIGV2ZW4gbnVtYmVycwogICAgICovCiAgICBpZigkbnVtICUgMiA9PSAwKSB7CiAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgfQoKICAgIC8qKgogICAgICogQ2hlY2tzIHRoZSBvZGQgbnVtYmVycy4gSWYgYW55IG9mIHRoZW0gaXMgYSBmYWN0b3IsIHRoZW4gaXQgcmV0dXJucyBmYWxzZS4KICAgICAqIFRoZSBzcXJ0IGNhbiBiZSBhbiBhcHJveGltYXRpb24sIGhlbmNlIGp1c3QgZm9yIHRoZSBzYWtlIG9mCiAgICAgKiBzZWN1cml0eSwgb25lIHJvdW5kcyBpdCB0byB0aGUgbmV4dCBoaWdoZXN0IGludGVnZXIgdmFsdWUuCiAgICAgKi8KICAgICRjZWlsID0gY2VpbChzcXJ0KCRudW0pKTsKICAgIGZvcigkaSA9IDM7ICRpIDw9ICRjZWlsOyAkaSA9ICRpICsgMikgewogICAgICAgIGlmKCRudW0gJSAkaSA9PSAwKQogICAgICAgICAgICByZXR1cm4gZmFsc2U7CiAgICB9CgogICAgcmV0dXJuIHRydWU7Cn0KCiRpbnB1dHM9YXJyYXkoKTsKd2hpbGUoJGY9ZmdldHMoU1RESU4pKQp7CglhcnJheV9wdXNoKCRpbnB1dHMsJGYpOwp9CgokbnVtX3Rlc3RzPSRpbnB1dHNbMF07CmlmKCRudW1fdGVzdHM8PTEwMCkKewoJZm9yKCRpPTA7JGk8JG51bV90ZXN0czskaSsrKQoJewoJCSRzdHJsZW49JGlucHV0c1skaSoyKzFdOwoJCSRzdHI9JGlucHV0c1skaSoyKzJdOwoJCWlmKCRzdHJsZW4+PTEgJiYgJHN0cmxlbjw9NTAwKQoJCXsKCQkJJHN0cl9hcnI9c3RyX3NwbGl0KCRzdHIpOwoJCQkkYXJyX2FzY2lpPWFycmF5X21hcChmdW5jdGlvbigkdmFsKXsKCQkJCXJldHVybiBvcmQoJHZhbCk7CgkJCQl9LCRzdHJfYXJyKTsKCQkJJGFycl91cGRhdGVkPWFycmF5X21hcChmdW5jdGlvbigkdmFsKXsKCQkJICAgICRtYWluX3ByaW1lPSR2YWw7CgkJCSAgICBpZigoKCR2YWw+PTY1ICYmICR2YWw8PTkwKXx8KCR2YWw+PTk3ICYmICR2YWw8PTEyMikpICYmICFpc1ByaW1lKCR2YWwpKQoJCQkgICAgewoJCQkgICAgICAgICR0cnV0aD1mYWxzZTsKCQkJICAgICAgICAkaT0xOwoJCQkgICAgICAgIHdoaWxlKCEkdHJ1dGgpewoJCQkgICAgICAgICAgICAkdXBkYXRlZF9vbmU9JHZhbCskaTsKCQkJICAgICAgICAgICAgJHRydXRoPWlzUHJpbWUoJHVwZGF0ZWRfb25lKTsKCQkJICAgICAgICAgICAgKyskaTsKCQkJICAgICAgICB9CgkJCSAgICAgICAgCgkJCSAgICAgICAgJG54dF9wcmltZT0kdXBkYXRlZF9vbmU7Ly8xMjcKCQkJICAgICAgICAvLyRtYXlfcHJlX3ByaW1lPSR2YWwtKCRueHRfcHJpbWUtJHZhbCk7Ly8xMTUKCQkJICAgICAgICBmb3IoJGs9NjU7JGs8JHZhbDskaysrKQoJCQkgICAgICAgIHsKCQkJICAgICAgICAgICAgaWYoaXNQcmltZSgkaykgJiYgKCRueHRfcHJpbWUtJHZhbCA+PSAkdmFsLSRrIHx8ICRueHRfcHJpbWUgPiBvcmQoJ3onKSkpCgkJCSAgICAgICAgICAgICAgICAkbWFpbl9wcmltZT0kazsKCQkJICAgICAgICB9CgkJCSAgICAgICAgCgkJCSAgICAgICAgaWYoJG1haW5fcHJpbWU9PSR2YWwpCgkJCSAgICAgICAgICAgICRtYWluX3ByaW1lPSRueHRfcHJpbWU7CgkJCSAgICB9CgkJCSAgICBlbHNlIGlmKCRtYWluX3ByaW1lIT0xMCAmJiAoJG1haW5fcHJpbWU8NjUgfHwgJG1haW5fcHJpbWU+MTIyICkKCQkJICAgICAgICAkbWFpbl9wcmltZT02NzsKCQkJICAgIHJldHVybiBjaHIoJG1haW5fcHJpbWUpOwoJCQl9LCRhcnJfYXNjaWkpOwoJCQllY2hvIGltcGxvZGUoIiIsJGFycl91cGRhdGVkKS4iXG4iOwoJCX0KCQoJfQoKfQoKCj8+Cg==

MgozNzUKQXZmbWFMZ0xScFFhZEx5VGhzeFZ6a1VxYkZPZHhmYkxHZHBCV093bUFuZmxFTmxZRmJkaE5IZXJIVnRaa2FQTGdNdE5Rb3ZWSHB3R2ZISmRYWFdBaFlyaHdYS1B4dG5weENJc2FYVkFrY3hUcFZwckZOZU9WY25TRXNnSXZmcVhQUlNVQVNTREN2QUdyRkpDRGJ6R0xGaHJNWVdBTEVsQ2htdXJMckVlUXR0SVdjdHloUVh6WlVWQVl1Q0laZWNCSmJYTXhsTUhGYlp4SlJUU1pKbVpBd0NnZ0dhYlZzb3ZxQnJkbW1iQ1RhSUhEZlV1bkxGbnRmR3pvZEtxb0FLd0Nhc3NLTUR5YmV0aFJhUWdlZ3NPYXdmTkNOcklBa0VDRUtwYndFbGh2V3RsWkJFWnFKUXBFa3pwaVNqcnFaWklIYnN6VXh3dVdyZVhreEZLeFNBaUtvZW1JcUVUR1Z4Y0Nqd2VLaGJ5WHhoVktDYk5UUUJLZ0hECjIwCkFXR3JPd1VjRlduZ2h0QXl2eFNi

2
375
AvfmaLgLRpQadLyThsxVzkUqbFOdxfbLGdpBWOwmAnflENlYFbdhNHerHVtZkaPLgMtNQovVHpwGfHJdXXWAhYrhwXKPxtnpxCIsaXVAkcxTpVprFNeOVcnSEsgIvfqXPRSUASSDCvAGrFJCDbzGLFhrMYWALElChmurLrEeQttIWctyhQXzZUVAYuCIZecBJbXMxlMHFbZxJRTSZJmZAwCggGabVsovqBrdmmbCTaIHDfUunLFntfGzodKqoAKwCassKMDybethRaQgegsOawfNCNrIAkECEKpbwElhvWtlZBEZqJQpEkzpiSjrqZZIHbszUxwuWreXkxFKxSAiKoemIqETGVxcCjweKhbyXxhVKCbNTQBKgHD
20
AWGrOwUcFWnghtAyvxSb