//求阶模板：A^x=1(mod M),调用GetJie(A,M)

//输入：10^10>A,M>1

//输出：无解返回-1，有解返回最小正整数x

//复杂度：O(M^(0.5))

long long gcd(long long a,long long b)

{

    if(b==) return a;

    return gcd(b,a%b);

}

//欧拉函数:复杂度O(n^(0.5)),返回[1,n-1]中所有和n互素的数的个数和

long long phi(long long x)

{

    long long sum=x;

    for(long long i=;i*i<=x;i++)

    {

        if(x%i==)

        {

            sum=sum-sum/i;

            while(x%i==) x/=i;

        }

    }

    if(x!=) sum=sum-sum/x;

    return sum;

}

long long Mod_Mul(long long a,long long b,long long mod)

{

    long long sum=;

    while(b)

    {

        if(b&) sum=(sum+a)%mod;

        b>>=;

        a = (a+a)%mod;

    }

    return sum;

}

//a^b%mod 快速幂

long long Quk_Mul(long long a,long long b,long long mod)

{

    long long qsum=;

    while(b)

    {

        if(b&) qsum=Mod_Mul(qsum,a,mod);

        b>>=;

        a=Mod_Mul(a, a, mod);

    }

    return qsum;

}

long long GetJie(long long A,long long M)

{

    long long d = gcd(A,M);

    if(d != ) return -;

    long long m=phi(M);

    //然后对m进行拆分

    long long prm[],prmcnt[];

    int pcnt=;

    memset(prmcnt,,sizeof(prmcnt));

    long long tm = m;

    for(long long i=;i*i<=tm;i++)

    {

        if(tm%i==)

        {

            prm[pcnt]=i;

            while(tm%i==)

            {

                prmcnt[pcnt]++;

                tm/=i;

            }

            pcnt++;

        }

    }

    if(tm!=)

    {

        prm[pcnt]=tm;

        prmcnt[pcnt]=;

        pcnt++;

    }

    for(int i=;i<pcnt;i++)

    {

        for(int j=;j<prmcnt[i];j++)

        {

            if( Quk_Mul(A, m/prm[i], M)== )

            {

                m/=prm[i];

            }

        }

    }

    return m;

}

//求阶模板：A^x=1(mod M),调用GetJie(A,M)

//输入：10^10>A,M>1

//输出：无解返回-1，有解返回最小正整数x

//复杂度：M^(0.5)

long long PRIME[];

long long gcd(long long a,long long b)

{

    if(b==) return a;

    return gcd(b,a%b);

}

//欧拉函数:复杂度O(n^(0.5)),返回[1,n-1]中所有和n互素的数的个数和

long long phi(long long x)

{

    long long sum=x;

    long long p = PRIME[];

    for(int i=;p*p<=x;i++)

    {

        if( == x%p)

        {

            sum=sum-sum/p;

            while(x%p==) x/=p;

        }

        p=PRIME[i+];

    }

    if(x!=) sum=sum-sum/x;

    return sum;

}

long long Mod_Mul(long long a,long long b,long long mod)

{

    long long sum=;

    while(b)

    {

        if(b&) sum=(sum+a)%mod;

        b>>=;

        a = (a+a)%mod;

    }

    return sum;

}

//a^b%mod 快速幂

long long Quk_Mul(long long a,long long b,long long mod)

{

    long long qsum=;

    while(b)

    {

        if(b&) qsum=Mod_Mul(qsum,a,mod);//mod不是很大的时候这一步可以去掉

        b>>=;

        a=Mod_Mul(a, a, mod);//

    }

    return qsum;

}

long long GetJie(long long A,long long M)

{

    long long d = gcd(A,M);

    if(d != ) return -;

    long long m=phi(M);

    //然后对m进行拆分

    long long prm[],prmcnt[];

    int pcnt=;

    memset(prmcnt,,sizeof(prmcnt));

    long long tm = m;

    long long p=PRIME[];

    for(long long i=;p*p<=tm;i++)

    {

        if(tm%p==)

        {

            prm[pcnt]=p;

            while(tm%p==)

            {

                prmcnt[pcnt]++;

                tm/=p;

            }

            pcnt++;

        }

        p=PRIME[i+];

    }

    if(tm!=)

    {

        prm[pcnt]=tm;

        prmcnt[pcnt]=;

        pcnt++;

    }

    for(int i=;i<pcnt;i++)

    {

        for(int j=;j<prmcnt[i];j++)

        {

            if( Quk_Mul(A, m/prm[i], M)== )

            {

                m/=prm[i];

            }

        }

    }

    return m;

}

void getprime(long long up)

{

    bool pmark[];

    memset(pmark,,sizeof(pmark));

    int pcnt=;

    PRIME[pcnt++]=;

    for(int i=;i<=up;i+=) pmark[i]=;

    for(int i=;i<=up;i+=)

    {

        if(pmark[i]==)

        {

            PRIME[ pcnt++ ] = i;

            for(int j=i+i;j<=up;j+=i)

            {

                pmark[j]=;

            }

        }

    }

}