Perioada1

// prof. Pit - Rada Ionel Vasile
// O(sqrt(n)+sqrt(fi(n))*log(fi(n)))

#include<fstream>
#define baza 100000
using namespace std;
ifstream  fin("perioada1.in");
ofstream fout("perioada1.out");

long long N;
void prod(long long a[], long long b[]){
    long long t,c[5]={0,0,0,0,0};
    int i,j;
    for(i=0;i<=2;i++){
        for(j=0;j<=2;j++){
            c[i+j]=c[i+j]+a[i]*b[j];
        }
    }
    t=0;
    for(i=0;i<=4;i++){
        t=t+c[i];
        c[i]=t%baza;
        t=t/baza;
    }
    for(i=0;i<=4;i++){
        a[i]=c[i];
    }
}

void modulo(long long a[], long long MOD){
    long long r;
    r=a[4];
    int i;
    for(i=3;i>=0;i--){
        r=(r*baza+a[i])%MOD;
    }
    for(i=0;i<=4;i++){
        a[i]=r%baza;
        r=r/baza;
    }
}

long long p10(long long b, long long MOD){
    long long r,p[5]={1,0,0,0,0},a[5]={10,0,0,0,0};
    int i;
    while(b){
        if(b%2==1){
            ///p=(p*a)%MOD;
            prod(p,a);
            modulo(p,MOD);
        }
        b=b/2;
        ///a=(a*a)%MOD;
        prod(a,a);
        modulo(a,MOD);
    }
    r=0;
    for(i=2;i>=0;i--){
        r=r*baza+p[i];
    }
    return r;
}

int main(){
    long long fi,x,d,p,perioada;
    long long c;
    fin>>N;
    fi=N;
    x=N;

    c=0;
    while(x%2==0){
        x=x/2;
        c++;
    }
    if(c){
        fi=fi/2;
    }
    d=3;
    while(d*d<=x){
        c=0;
        while(x%d==0){
            x=x/d;
            c++;
        }
        if(c){
            fi=fi/d*(d-1);
        }
        d=d+2;
    }
    if(x>1){
        fi=fi/x*(x-1);
    }
    perioada=0;
    for(d=1;d*d<fi;d++){
        if(fi%d==0){
            // fout<<d<<"\n";
            p=p10(d,N);
            if(p==1){
                perioada=d;
                break;
            }
        }
    }
    if(perioada==0 && d*d==fi){
        // fout<<d<<"\n";
        p=p10(d,N);
        if(p==1){
            perioada=d;
        }
    }
    if(perioada==0){
        for(d=d-1;d>=1;d--){
            if(fi%d==0){
                // fout<<fi/d<<"\n";
                p=p10(fi/d,N);
                if(p==1){
                    perioada=fi/d;
                    break;
                }
            }
        }
    }
    fout<<perioada<<"\n";
    fout.close();
    fin.close();
    return 0;
}