Prime Driving Conditions

Meredith just bought a new car and needs license plates. A Pennsylvania plate is three uppercase letters followed by a four digit number. Plates are handed out in lexicographic order. AAA 0000 goes out first, then AAA 0001, then AAA 0002. After AAA 9999 comes AAB 0000, and after AZZ 9999 comes BAA 0000. The very last plate is ZZZ 9999.

Most people take whatever plate comes up next. Meredith does not. She insists that the four digit number on her plate is a prime. A prime is a number greater than 1 whose only divisors are 1 and itself. The smallest primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, and so on.

If Meredith walks into the licensing office and the next plate available is JPB 1285, she waits for JPB 1289, because 1289 is the smallest prime that is at least 1285. If the next plate available had been JPB 9999, she would have waited for JPC 0002.

You are given a starting plate. Find the first plate that is lexicographically equal to or later than it and whose four digit number is prime.

As a side note, the prime $2^{74207281} - 1$, found in January 2016, has 22,338,618 digits. That is far too long for a license plate.

The input holds several test cases, one per line. Each line has a string of three uppercase letters, one space, and a four digit number. The string is never ZZZ. The number runs from 0000 to 9999 and is always written with four digits, padded with leading zeros.

The line END 0000 ends the input and is not a test case. A line whose letters are END and whose number is not 0000 is an ordinary test case.

For each test case, print the plate Meredith accepts on its own line. Print three uppercase letters, one space, and the four digit number padded with leading zeros to four digits.