#include<stdio.h>#include<cstdlib>#include<time.h>#include<cstring>int n;int len;int num[30];int isyes;int v[30];unsigned long long Multi(unsigned long long a, unsigned long long b, unsigned long long n){unsigned long long back = 0, temp = a%n;while (b){if ((b & 1) && ((back += temp) >= n) ) back -= n;if ((temp <<= 1) >= n) temp -= n; b >>= 1;} return back;}unsigned long long Pow(unsigned long long a, unsigned long long b, unsigned long long c){unsigned long long ans = 1; while (b != 0) {if (b & 1) ans = Multi(ans, a, c);a = Multi(a, a, c);b >>= 1; } return ans;}int s(unsigned long long n){int p = 0;for (int i = 0; i < 50; i++){int q = 0;unsigned long long x = rand()%n;while (x == 0)x = rand()%n;unsigned long long y = n - 1;while (y%2 == 0){y = y/2;unsigned long long m = Pow(x, y, n);if (m == n - 1){q = 1;break;}}unsigned long long m = Pow(x, y, n);if (m == 1 || m == n - 1)q = 1;if (q == 0){p = 1;break;}}return p;}int judge(long long n){if (n == 2){return 1;}if (n%2 == 0 || n == 1){return 0;}int p = s(n);if (p)return 0;elsereturn 1;}void print(){for(int i=len-1; i>=0; i--)if(num[i]>=0 && num[i]<=9)printf("%d", num[i]);elseprintf("%c", num[i]-10+'A');printf("n");}void dfs(int depth){if(isyes==1)return ;if(depth == -1){long long a = 0, b = 0;for(int i=0; i<len; i++)a = a*n + num[i];for(int i=len-1; i>=0; i--)b = b*n + num[i];if(judge(a) && judge(b)){print();isyes = 1;}return ;}for(int i=n-1 ; i> 0;i--){if(v[i]==0 && i<num[depth+1]){v[i]=1;num[depth]=i;dfs(depth-1);v[i]=0;}}}int main(){srand((unsigned)time(0));while(scanf("%d", &n) != EOF){isyes = 0;for(len=n; len>0; len--){memset(v,0,sizeof(v));num[len] = n;dfs(len-1);}if(!isyes)printf("not specialn");}}
