/*
  ID:twd30651
  PROG:palsquare
  LANG:C++
*/
#include<iostream>
#include<fstream>
#include<stdlib.h>
#include<string.h>
using namespace std;
int BASE;
char B[]={'0','1','2','3','4','5','6','7','8','9',
          'A','B','C','D','E','F','G','H','I','J'};
int isPalindrome(char *s,int len)
{

    for(int i=0,j=len-1;i<=j;i++,j--)
    {
        if(s[i]!=s[j])return 0;
    }
    if(len>0)return 1;
    else return 0;
}
void getp(char *s,int num,int b)
{
    int index=0;
    while(num/b!=0)
    {
        s[index++]=B[num%b];
        num=num/b;
    }
    s[index++]=B[num%b];;
    s[index]='\0';
//    printf("%s\n",s);
}
int main(int argc,char *argv[])
{
    freopen("palsquare.in","r",stdin);
    freopen("palsquare.out","w",stdout);
    scanf("%d",&BASE);
    char s[20];
    char t[20];
    for(int i=1;i<=300;++i)
    {
        memset(s,0,sizeof(s));
        memset(t,0,sizeof(t));
        getp(s,i*i,BASE);
        if(isPalindrome(s , strlen(s)))
        {
            getp(t,i,BASE);
            int l=strlen(t);
            for(int j=0;j<l/2;++j)
            {
                char tmp=t[j];
                t[j]=t[l-j-1];
                t[l-j-1]=tmp;
            }

            printf("%s %s\n",t,s);
        }
    }

    return 0;
}

USACO 1.2 Palindromic Squares (进制转换，回文)