AIOC Banner

Problem: Anagrammatic Primes

Want to try solving this problem? You can submit your code online if you log in or register.


Anagrammatic Primes

Input File: primes.in
Output File: primes.out
Time Limit: 0.1 second

A number is "prime" if it has no divisors other than itself and 1. For example, 23 is prime but 35 is not prime because 35 = 7 x 5. If the digits of a number are rearranged, then usually its primeness changes — for example, 35 is not prime but 53 is. For this problem, you must find numbers which are prime no matter how you rearrange their digits. For example, all of the numbers 113, 131 and 311 are prime, so we say that 113 is an "anagrammatic prime" (also 131 and 311 are anagrammatic primes).

Input

Input will consist of a single line containing a single positive integer n (1 <= n < 10,000,000). You must find the first anagrammatic prime that is larger than n but less than the next power of ten above n.

Output

Output must be a single number. This number must either be the next anagrammatic prime as described above, or 0 if there is no anagrammatic prime in the range defined.

Sample Input 1

10

Sample Output 1

11

Sample Input 2

900

Sample Output 2

919

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 15 November 2019,  6:21am AEDT