Description

   Have you heard the fact "The base of every normal number system is 10" ? Of course, I am not talking about number systems like Stern Brockot Number System. This problem has nothing to do with this fact but may have some similarity. 

   You will be given an N based integer number R and you are given the guaranty that R is divisible by (N-1). You will have to print the smallest possible value for N. The range for N is 2 <= N <= 62 and the digit symbols for 62 based number is (0..9 and A..Z and a..z). Similarly, the digit symbols for 61 based number system is (0..9 and A..Z and a..y) and so on.

Input

   Each line in the input will contain an integer (as defined in mathematics) number of any integer base (2..62). You will have to determine what is the smallest possible base of that number for the given conditions. No invalid number will be given as input. The largest size of the input file will be 32KB.

Output

   If number with such condition is not possible output the line "such number is impossible!" For each line of input there will be only a single line of output. The output will always be in decimal number system.

Sample Input

    3
    5
    A

Sample Output

    4
    6
    11
题意：
设输入的是abcd，假设其解是n进制，则有（a*n*n*n + b*n*n + c*n + d)%(n-1)=0 则有：( (a*n*n*n)%(n-1)+(b*n*n)%(n-1)+(c*n)%(n-1)+d)%(n-1)=0  则有：（(a* (n%(n-1))*(n%(n-1))*(n%(n-1)))+(b* (n%(n-1)) *(n%(n-1)))+(c* (n%(n-1) +d ) %(n-1)=0  则有: (a*1*1*1+b*1*1+c*1+d)%(n-1)=0 则有：(a+b+c+d)%(n-1)=0
这样看来就是把所有数字的每一位加起来看看能除尽那一个进制-1就输出就完事了，但是细节还是要注意的！
ac代码如下：


///@zhangxiaoyu
///2015/8/13

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;

char ss[1000000];
int a[63]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,
          27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,
          51,52,53,54,55,56,57,58,59,60,61};///其实完全不用打表，我太笨了，聪明的你已经想到不用打表的做法了吧
int main()
{
    while(scanf("%s",ss)!=EOF)
    {
        int i;
        int len=strlen(ss);
        int sum=0;
        int index=-1;
        for(int i=0;i<len;i++)
        {
            if(isdigit(ss[i]))
            {
                sum+=a[ss[i]-'0'];
                index=max(index,a[ss[i]-'0']);
            }
            else if(islower(ss[i]))
            {
                sum+=a[ss[i]-'a'+36];
                index=max(index,a[ss[i]-'a'+36]);
            }
            else
            {
                sum+=a[ss[i]-'A'+10];
                index=max(index,a[ss[i]-'A'+10]);
            }
        }
        ///printf("%d %d\n",index,sum);
        bool flag=false;
        for(i=index;i<=61;i++)
        {
            if(sum%i==0)
            {
                printf("%d\n",i+1);
                flag=true;
                break;
            }
        }
        if(!flag)
            printf("such number is impossible!\n");
    }
    return 0;
}