#include <bits/stdc++.h>
using namespace std;


//入力が必ず-mod<a<modの時.
template<const int mod>
struct modint{ //mod変更が不可能.
    public:
    long long v = 0;
    static void setmod(int m){} //飾り.
    static constexpr long long getmod(){return mod;}
    modint(){v = 0;} modint(int a){v = a<0?a+mod:a;} modint(long long a){v = a<0?a+mod:a;}
    modint(unsigned int a){v = a;} modint(unsigned long long a){v = a;}
    long long val()const{return v;}
 
    modint &operator=(const modint &b) = default;
    modint operator+()const{return (*this);}
    modint operator-()const{return modint(0)-(*this);}
    modint operator+(const modint b)const{return modint(v)+=b;}
    modint operator-(const modint b)const{return modint(v)-=b;}
    modint operator*(const modint b)const{return modint(v)*=b;}
    modint operator/(const modint b)const{return modint(v)/=b;}
    modint operator+=(const modint b){
        v += b.v; if(v >= mod) v -= mod;
        return *this;
    }
    modint operator-=(const modint b){
        v -= b.v; if(v < 0) v += mod; 
        return *this;
    }   
    modint operator*=(const modint b){v = v*b.v%mod; return *this;}
    modint operator/=(modint b){ //b!=0 mod素数が必須.
        if(b == 0) assert(false);
        int left = mod-2;
        while(left){if(left&1) *this *= b; b *= b; left >>= 1;}
        return *this;
    }
    modint operator++(){*this += 1; return *this;}
    modint operator--(){*this -= 1; return *this;}
    modint operator++(int){*this += 1; return *this;}
    modint operator--(int){*this -= 1; return *this;}
    bool operator==(const modint b)const{return v == b.v;}
    bool operator!=(const modint b)const{return v != b.v;}
    bool operator>(const modint b)const{return v > b.v;}
    bool operator>=(const modint b)const{return v >= b.v;}
    bool operator<(const modint b)const{return v < b.v;}
    bool operator<=(const modint b)const{return v <= b.v;}
    modint pow(long long n)const{
        modint ret = 1,p = v;
        if(n < 0) p = p.inv(),n = -n;
        while(n){
            if(n&1) ret *= p;
            p *= p; n >>= 1;
        }
        return ret;
    }
    modint inv()const{return modint(1)/v;} //素数mod必須.
};
using mint = modint<998244353>;
namespace to_fold{
__int128_t safemod(__int128_t a,long long m){a %= m; if(a < 0) a += m; return a;}
pair<long long,long long> invgcd(long long a,long long b){
    //return {gcd(a,b),x} (xa≡g(mod b))
    a = safemod(a,b);
    if(a == 0) return {b,0};
    long long x = 0,y = 1,memob = b;
    while(a){
        long long q = b/a;
        b -= a*q;
        swap(x,y); y -= q*x;
        swap(a,b);
    }
    if(x < 0) x += memob/b;
    return {b,x};
}
template<long long mod>
long long Garner(const vector<long long> &A,const vector<long long> &M){
    __int128_t mulM = 1,x = A.at(0)%M.at(0); //Mの要素のペア互いに素必須.
    for(int i=1; i<A.size(); i++){
        //assert(gcd(mulM,M.at(i-1)) == 1);
        mulM *= M.at(i-1); //2乗がオーバーフローする時__int128_t
        long long t = safemod((A.at(i)-x)*invgcd(mulM,M.at(i)).second,M.at(i));
        x += t*mulM;
    }
    return x%mod;
}
int countzero(unsigned long long x){
    if(x == 0) return 64;
    else return __popcount((x&-x)-1);
}
template<typename mint>
struct fftinfo{
    static bool First;
    static mint g,sum_e[30],sum_ie[30]; //sum_e[i]=Π[j=0~i-1]ies[j] * es[i],sum_ie[i]=Π[i=0~j-1]es[j] * ies[i].
    static mint divpow2[30]; //div[i] = 1/(2^i).
    static mint Zeta[30];
    fftinfo(){
        if(!First) return;
        First = false;
        const long long mod = mint::getmod();
        if(mod == 998244353) g = 3;
        else if(mod == 754974721) g = 11;
        else if(mod == 167772161) g = 3;
        else if(mod == 469762049) g = 3;
        else assert(false); //現状RE.
        mint es[30],ies[30]; //es[i]^(2^(2+i))=1.
        int cnt2 = countzero(mod-1);
        mint e = g.pow((mod-1)>>cnt2),ie = e.inv();
        for(int i=cnt2; i>=2; i--){ //e^(2^i)=1;
            es[i-2] = e,e *= e;
            ies[i-2] = ie,ie *= ie;
        }
        mint rot = 1;
        for(int i=0; i<=cnt2-2; i++) sum_e[i] = es[i]*rot,rot *= ies[i];
        rot = 1;
        for(int i=0; i<=cnt2-2; i++) sum_ie[i] = ies[i]*rot,rot *= es[i];
        mint div2n = 1,div2 = mint(1)/2;
        for(int i=0; i<30; i++) divpow2[i] = div2n,div2n *= div2;
        for(int i=0; i<=cnt2; i++) Zeta[i] = g.pow((mod-1)/(2<<i));
    }
};
template<typename mint> bool fftinfo<mint>::First=true;
template<typename mint> mint fftinfo<mint>::g;
template<typename mint> mint fftinfo<mint>::sum_e[30];
template<typename mint> mint fftinfo<mint>::sum_ie[30];
template<typename mint> mint fftinfo<mint>::divpow2[30];
template<typename mint> mint fftinfo<mint>::Zeta[30];
template<typename mint>
void NTT(vector<mint> &A){ //ACLを超参考にしてる.
    int n = A.size();
    assert((n&-n) == n);
    fftinfo<mint> info;
    int h = countzero(n);
    for(int ph=1; ph<=h; ph++){
        int w = 1<<(ph-1),p = 1<<(h-ph);
        mint rot = 1;
        for(int s=0; s<w; s++){
            int offset = s<<(h-ph+1);
            for(int i=0; i<p; i++){
                mint l = A.at(i+offset),r = A.at(i+offset+p)*rot;
                A.at(i+offset) = l+r;
                A.at(i+offset+p) = l-r;
            }
            rot *= info.sum_e[countzero(~(unsigned int)(s))];
        }
    }
}
template<typename mint>
void INTT(vector<mint> &A){
    int n = A.size();
    assert((n&-n) == n);
    fftinfo<mint> info;
    const unsigned int mod = mint::getmod();
    int h = countzero(n);
    for(int ph=h; ph>0; ph--){
        int w = 1<<(ph-1),p = 1<<(h-ph);
        mint irot = 1;
        for(int s=0; s<w; s++){
            int offset = s<<(h-ph+1);
            for(int i=0; i<p; i++){
                mint l = A.at(i+offset),r = A.at(i+offset+p);
                A.at(i+offset) = l+r;
                A.at(i+offset+p) = ((unsigned long long)(mod+(unsigned int)l.v-(unsigned int)r.v)*irot.v)%mod;
            }
            irot *= info.sum_ie[countzero(~(unsigned int)(s))];
        }
    }
    mint divn = info.divpow2[h];
    for(auto &a : A) a *= divn;
}
template<typename mint>
vector<mint> convolution(vector<mint> A,vector<mint> B){ //mintじゃないのを突っ込まないように!!!.
    int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1,N = 1;
    if(siza == 0 || sizb == 0) return {};
    if(min(siza,sizb) <= 60){ //naive.
        vector<mint> ret(sizc);
        if(siza >= sizb){for(int i=0; i<siza; i++) for(int k=0; k<sizb; k++) ret.at(i+k) += A.at(i)*B.at(k);}
        else{for(int i=0; i<sizb; i++) for(int k=0; k<siza; k++) ret.at(i+k) += B.at(i)*A.at(k);}
        return ret;
    }
    while(N < sizc) N <<= 1;
    A.resize(N),B.resize(N);
    NTT(A); NTT(B);
    for(int i=0; i<N; i++) A.at(i) *= B.at(i);
    INTT(A); A.resize(sizc);
    return A;
}
vector<long long> convolution_ll(const vector<long long> &A,const vector<long long> &B){ //long longに収まる範囲.
    int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1;
    if(siza == 0 || sizb == 0) return {};
    vector<long long> ret(sizc);
    if(min(siza,sizb) <= 200){ //naive 200はやばい?.
        vector<long long> ret(sizc);
        if(siza >= sizb){for(int i=0; i<siza; i++) for(int k=0; k<sizb; k++) ret.at(i+k) += A.at(i)*B.at(k);}
        else{for(int i=0; i<sizb; i++) for(int k=0; k<siza; k++) ret.at(i+k) += B.at(i)*A.at(k);}
        return ret;
    }
    const unsigned long long mod1 = 754974721,mod2 = 167772161,mod3 = 469762049;
    const unsigned long long m1m2 = mod1*mod2,m2m3 = mod2*mod3,m3m1 = mod3*mod1,m1m2m3 = mod1*mod2*mod3;
    const unsigned long long i1 = invgcd(m2m3,mod1).second,i2 = invgcd(m3m1,mod2).second,i3 = invgcd(m1m2,mod3).second;
    assert(sizc <= (1<<24));
    using mint1 = modint<mod1>;
    using mint2 = modint<mod2>;
    using mint3 = modint<mod3>;
    vector<mint1> a1(siza),b1(sizb);
    vector<mint2> a2(siza),b2(sizb);
    vector<mint3> a3(siza),b3(sizb);
    for(int i=0; i<siza; i++) a1.at(i) = A.at(i)%mod1;
    for(int i=0; i<sizb; i++) b1.at(i) = B.at(i)%mod1;
    vector<mint1> C1 = convolution(a1,b1);
    for(int i=0; i<siza; i++) a2.at(i) = A.at(i)%mod2;
    for(int i=0; i<sizb; i++) b2.at(i) = B.at(i)%mod2;
    vector<mint2> C2 = convolution(a2,b2);
    for(int i=0; i<siza; i++) a3.at(i) = A.at(i)%mod3;
    for(int i=0; i<sizb; i++) b3.at(i) = B.at(i)%mod3;
    vector<mint3> C3 = convolution(a3,b3);
    vector<unsigned long long> offset = {0,0,m1m2m3,2*m1m2m3,3*m1m2m3};
    for(int i=0; i<sizc; i++){
        unsigned long long x = 0;
        x += (C1.at(i).v*i1)%mod1*m2m3;
        x += (C2.at(i).v*i2)%mod2*m3m1;
        x += (C3.at(i).v*i3)%mod3*m1m2;
        long long diff = C1.at(i).v-((long long)x+(long long)mod1)%mod1;
        if(diff < 0) diff += mod1;
        x -= offset.at(diff%5);
        ret.at(i) = x;
    }
    return ret;
}
template<typename mint>
vector<mint> convolution_llmod(const vector<mint> &A,const vector<mint> &B){
    int siza = A.size(),sizb = B.size(),sizc = siza+sizb-1;
    if(siza == 0 || sizb == 0) return {};
    vector<mint> ret(sizc);
    if(min(siza,sizb) <= 200){
        for(int i=0; i<siza; i++) for(int k=0; k<sizb; k++) ret.at(i+k) += A.at(i)*B.at(k);
        return ret;
    }
    const long long mod1 = 754974721,mod2 = 167772161,mod3 = 469762049;
    assert(sizc <= (1<<24));
    using mint1 = modint<mod1>;
    using mint2 = modint<mod2>;
    using mint3 = modint<mod3>;
    vector<mint1> a1(siza),b1(sizb);
    vector<mint2> a2(siza),b2(sizb);
    vector<mint3> a3(siza),b3(sizb);
    for(int i=0; i<siza; i++) a1.at(i) = A.at(i).v%mod1;
    for(int i=0; i<sizb; i++) b1.at(i) = B.at(i).v%mod1;
    vector<mint1> C1 = convolution(a1,b1);
    for(int i=0; i<siza; i++) a2.at(i) = A.at(i).v%mod2;
    for(int i=0; i<sizb; i++) b2.at(i) = B.at(i).v%mod2;
    vector<mint2> C2 = convolution(a2,b2);
    for(int i=0; i<siza; i++) a3.at(i) = A.at(i).v%mod3;
    for(int i=0; i<sizb; i++) b3.at(i) = B.at(i).v%mod3;
    vector<mint3> C3 = convolution(a3,b3);
    for(int i=0; i<sizc; i++){
        vector<long long> A = {C1.at(i).v,C2.at(i).v,C3.at(i).v};
        vector<long long> M = {mod1,mod2,mod3};
        ret.at(i) = Garner<mint::getmod()>(A,M);
    }
    return ret;
}
vector<int> convolution_int(const vector<int> &A,const vector<int> &B){ //intに収まる範囲.
    if(A.size() == 0 || B.size() == 0) return {};
    vector<int> ret;
    if(min(A.size(),B.size()) <= 60){
        ret.resize(A.size()+B.size()-1);
        for(int i=0; i<A.size(); i++) for(int k=0; k<B.size(); k++) ret.at(i+k) += A.at(i)*B.at(k);
    }
    else{
        using mint1 = modint<998244353>;
        vector<mint1> X(A.size()),Y(B.size()),Z;
        for(int i=0; i<A.size(); i++) X.at(i) = A.at(i);
        for(int i=0; i<B.size(); i++) Y.at(i) = B.at(i);
        Z = convolution(X,Y);
        ret.resize(Z.size());
        for(int i=0; i<Z.size(); i++) ret.at(i) = Z.at(i).v;
    }
    return ret;
}
template<typename mint> 
void NTTdoubling(vector<mint> &A){ //NTTの原理を忘れているため何やってるのか意味が分からない NTT-friendly専用.
        //INTT->resize(2倍）->NTTの代わりにcopy->INTT->謎の操作->NTT->push sizeが小さい時は効率悪いらしいよ.
        int n = A.size();
        fftinfo<mint> info;
        vector<mint> B = A;
        INTT(B);
        mint rot = 1,zeta = info.Zeta[countzero(n)];
        for(auto &v : B) v *= rot,rot *= zeta;
        NTT(B); A.reserve(n<<1);
        for(auto &v : B) A.push_back(v); 
}
bool isNTTfriendly(long long mod){
    if(mod == 998244353 || mod == 754974721 || mod == 16777216 || mod == 469762049) return true;
    return false; //現状false 原子根求める機能を追加してから.
    int have2 = countzero(mod-1);
    return have2 >= 20;//とりあえず2^20でokとする;
}
}
using namespace to_fold;

struct bigint{
    //__int128_t以上の数にも対応.
    //計算量 普通O(桁数),掛け算O(桁数log桁数),割り算O(桁数log桁数)(重い).
    public:
    bool isMinus; //負かどうか.
    vector<int> V;//絶対値.
    //先頭の要素の方が小さい位 5108->{8,0,1,5}.
    private:
    void slide(){
        for(int i=0; i<V.size(); i++){
            int v = V.at(i);
            int div10 = v<0?(v+1)/10-1:v/10; //÷10切り捨て.
            if(div10 == 0) continue;
            if(i+1==V.size()) V.push_back(0);
            V.at(i+1) += div10; V.at(i) -= div10*10; 
        }
        while(V.size() && V.back() == 0) V.pop_back();
        if(V.size() == 0) isMinus = false;
    }
    int comp(const bigint &b){ //0->|a|<|b|,1->|a|>|b|,2->|a|==|b|.
        if(V.size() < b.V.size()) return 0;
        if(V.size() > b.V.size()) return 1;
        for(int i=V.size(); i--;){
            if(V.at(i) == b.V.at(i)) continue;
            return V.at(i)>b.V.at(i);
        }
        return 2;
    }
    public:
    bigint():isMinus(false),V({}){}
    template<typename T>
    bigint(T a){
        if(a < 0) isMinus = true,a = -a;
        else isMinus = false;
        V = {};
        while(a) V.push_back(a%10),a /= 10;
    }
    bigint(const string &s){
        V = {}; 
        if(s.size() == 0) isMinus = false;
        else{
            if(s.at(0) == '-') isMinus = true;
            else isMinus = false;
            for(int i=s.size(); i--;) V.push_back(s.at(i)-'0');
            if(isMinus) V.pop_back();
            while(V.size() && V.back() == '0') V.pop_back();
        }
    }
    bigint(const bigint &n){isMinus = n.isMinus; V = n.V;}

    bigint &operator=(const bigint &b) = default;
    bigint operator+(const bigint &b){
        bigint ret;
        if(isMinus == b.isMinus){
            ret = *this;
            ret.V.resize(max(V.size(),b.V.size()));
            for(int i=0; i<b.V.size(); i++) ret.V.at(i) += b.V.at(i);
        }
        else{
            int now = comp(b);
            if(now == 2) return bigint(0);
            if(now == 1){
                ret = *this;
                for(int i=0; i<b.V.size(); i++) ret.V.at(i) -= b.V.at(i);
            }
            else{
                ret = b;
                for(int i=0; i<V.size(); i++) ret.V.at(i) -= V.at(i);
            }
        }
        ret.slide(); return ret;
    }
    bigint operator-(const bigint &b){
        bigint ret;
        if(isMinus != b.isMinus){
            ret = *this;
            ret.V.resize(max(V.size(),b.V.size()));
            for(int i=0; i<b.V.size(); i++) ret.V.at(i) += b.V.at(i);
        }
        else{
            int now = comp(b);
            if(now == 2) return bigint(0);
            if(now == 1){
                ret = *this;
                for(int i=0; i<b.V.size(); i++) ret.V.at(i) -= b.V.at(i);
            }
            else{
                ret = b; ret.isMinus ^= 1;
                for(int i=0; i<V.size(); i++) ret.V.at(i) -= V.at(i);
            }
        }
        ret.slide(); return ret;
    }
    bigint operator*(const bigint &b){
        bigint ret; ret.isMinus = (isMinus^b.isMinus);
        ret.V = convolution_int(V,b.V);
        ret.slide(); return ret;
    }
    bigint operator/(const bigint &b){//b!=0.
        assert(b.V.size());
        bigint ret(0); ret.isMinus = isMinus^b.isMinus;
        if(bigint(1) == b) return (*this);
        if(b.V.size() < 64){
            auto a = *this;
            int n = (*this).V.size(),m = b.V.size();
            for(int i=n-1; i>=0; i--){
                int ok = 0;
                bigint now;
                for(int k=i; k<min(n,i+m+1); k++) now.V.push_back(a.V.at(k)); 
                int memo = now.size();
                while(now.V.size() && now.V.back() == 0) now.V.pop_back();
                for(int v=1; v<10; v++){
                    if(now >= b) now -= b,ok++;
                    else break;
                }
                now.V.resize(memo);
                for(int k=i; k<min(n,i+m+1); k++) a.V.at(k) = now.V.at(k-i);
                ret.V.push_back(ok);
            }
            reverse(ret.V.begin(),ret.V.end());
            while(ret.V.size() && ret.V.back() == 0) ret.V.pop_back();
            return ret;
        }
        //ニュートン法.
        int accu = 2,need = max(2,(int)V.size()-(int)b.V.size()+2);
        bigint invB(10),two(200);
        for(int i=0; i<6; i++){ //精度2桁までやる
            bigint one = invB*b;
            two.V.pop_back();
            while(two.V.size() < one.V.size()) two.V.push_back(0);
            while(two.V.size() > one.V.size()) two.V.pop_back();
            two.V.push_back(2);
            bigint next = invB*(two-one);
            invB.V.assign(2,0);
            invB.V.at(1) = next.V.back(); next.V.pop_back();
            invB.V.at(0) = next.V.back();
        }
        while(accu < need){ //精度倍々になる.
            bigint one = invB*b;
            two.V.pop_back();
            while(two.V.size() < one.V.size()) two.V.push_back(0);
            two.V.push_back(2);
            bigint next = invB*(two-one);
            accu = min(accu<<1,need);
            invB.V.clear();
            for(int i=max(0,(int)next.V.size()-accu); i<next.V.size(); i++) invB.V.push_back(next.V.at(i));
        }
        {   //精度足りてない場合があるのでラスト1回.
            bigint one = invB*b;
            two.V.pop_back();
            while(two.V.size() < one.V.size()) two.V.push_back(0);
            two.V.push_back(2);
            bigint next = invB*(two-one);
            accu = min(accu<<1,need);
            invB.V.clear();
            for(int i=max(0,(int)next.V.size()-accu); i<next.V.size(); i++) invB.V.push_back(next.V.at(i));
        }

        bigint check = (*this)*invB; //floor(check)=ret.
        for(int i=invB.V.size()+b.V.size()-1; i<check.V.size(); i++) ret.V.push_back(check.V.at(i));
        if((*this)-ret*b >= b){ //+1の可能性.
            int digit = 0;
            ret.V.push_back(0);
            ret.V.at(digit)++;
            while(ret.V.at(digit) == 10) ret.V.at(digit) = 0,ret.V.at(++digit)++;
            if(ret.V.back() == 0) ret.V.pop_back();
        }
        return ret;
    }
    bigint operator%(const bigint &b){ //a>=0,b>0を仮定.   
        bigint ret = *this;
        ret -= ret/b*b;
        return ret;
    }
    bigint operator+=(const bigint &b){return *this=*this+b;}
    bigint operator-=(const bigint &b){return *this=*this-b;}
    bigint operator*=(const bigint &b){return *this=*this*b;}
    bigint operator/=(const bigint &b){return *this=*this/b;}
    bigint operator%=(const bigint &b){return *this=*this%b;}
    
    bool operator==(const bigint &b){
        if(V.size() != b.V.size() || isMinus != b.isMinus) return false;
        return V == b.V;
    }
    bool operator<(const bigint &b){
        if(isMinus && !b.isMinus) return true;
        if(!isMinus && b.isMinus) return false;
        if(!isMinus && !b.isMinus){
            if(V.size() < b.V.size()) return true;
            if(V.size() > b.V.size()) return false;
            for(int i=V.size(); i--;){
                if(V.at(i) == b.V.at(i)) continue;
                return V.at(i) < b.V.at(i); 
            }
            return false;
        }
        else{
            if(V.size() > b.V.size()) return true;
            if(V.size() < b.V.size()) return false;
            for(int i=V.size(); i--;){
                if(V.at(i) == b.V.at(i)) continue;
                return V.at(i) > b.V.at(i);
            }
            return false;
        }
    }
    bool operator<=(const bigint &b){
        if(isMinus && !b.isMinus) return true;
        if(!isMinus && b.isMinus) return false;
        if(!isMinus && !b.isMinus){
            if(V.size() < b.V.size()) return true;
            if(V.size() > b.V.size()) return false;
            for(int i=V.size(); i--;){
                if(V.at(i) == b.V.at(i)) continue;
                return V.at(i) < b.V.at(i); 
            }
            return true;
        }
        else{
            if(V.size() > b.V.size()) return true;
            if(V.size() < b.V.size()) return false;
            for(int i=V.size(); i--;){
                if(V.at(i) == b.V.at(i)) continue;
                return V.at(i) > b.V.at(i);
            }
            return true;
        }
    }
    bool operator>(const bigint &b){return !(*this<=b);}
    bool operator>=(const bigint &b){return !(*this<b);}
    bool operator!=(const bigint &b){return !(*this==b);}
    unsigned int size(){return V.size();}
    mint get(){
        mint ret = 0,p10 = 1;
        for(auto v : V) ret += p10*v,p10 *= 10;
        return ret;
    }
};
istream &operator>>(istream &is,bigint &a){
    string s; cin >> s;
    a = bigint(s);
    return is;
}
ostream &operator<<(ostream &os,bigint a){
    if(a.isMinus) cout << "-";
    if(a.V.size() == 0) cout << 0;
    for(int i=a.V.size(); i--;) cout << a.V.at(i);
    return os;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    int Need = 100000;
    vector<int> allp;
    vector<bool> prime(Need+1,true);
    prime.at(0) = false; prime.at(1) = false;
    for(int i=2; i<=Need; i++){
        if(!prime.at(i)) continue;
        allp.push_back(i);
        for(long long k=((long long)i)*i; k<=Need; k+=i) prime.at(k) = false;
    }

    while(T--){
        bigint a,b,c; cin >> a >> b >> c;
        mint answer = 0;
        while(a%c == 0) answer += b.get(),a /= c;

        long long a1 = 0,a2 = 0,a3 = 0,p15 = 1'000'000'000'000'000LL;
        long long c1 = 0,c2 = 0,c3 = 0;
        auto divA = [&](int p) -> void {
            a /= p;
            while(a.V.size() <= 40) a.V.push_back(0);
            a1 = 0,a2 = 0,a3 = 0;
            for(int i=14; i>=0; i--){
                a1 *= 10,a1 += a.V.at(i);
            }
            for(int i=29; i>=15; i--){
                a2 *= 10,a2 += a.V.at(i);
            }
            for(int i=40; i>=30; i--){
                a3 *= 10,a3 += a.V.at(i);
            }
            while(a.V.back() == 0) a.V.pop_back();
        };
        auto divC = [&](int p) -> void {
            c /= p;
            while(c.V.size() <= 40) c.V.push_back(0); 
            c1 = 0,c2 = 0,c3 = 0;
            for(int i=14; i>=0; i--){
                c1 *= 10,c1 += c.V.at(i);
            }
            for(int i=29; i>=15; i--){
                c2 *= 10,c2 += c.V.at(i);
            }
            for(int i=40; i>=30; i--){
                c3 *= 10,c3 += c.V.at(i);
            }
            while(c.V.back() == 0) c.V.pop_back();
        };
        divA(1),divC(1);
        
        pair<int,int> worst = {1,1};
        auto chmin = [&](pair<int,int> check){if(worst.first*check.second > worst.second*check.first) worst = check;};
        for(auto p : allp){
            int one = 0,two = 0;
            while((a1%p+a2%p*(p15%p)+a3%p*(p15%p)*(p15%p))%p == 0) divA(p),one++;
            while((c1%p+c2%p*(p15%p)+c3%p*(p15%p)*(p15%p))%p == 0) divC(p),two++;
            if(two == 0) continue;
            chmin({one,two});
            if(one == 0) break;
        }
        if(worst.first != 0 && c != 1){
            bigint a2 = 1;
            vector<int> plus1;
            for(int i=0; i<20; i++){
                a2 *= a;
                if(a2%c == 0) a2 /= c,plus1.push_back(1);
                else plus1.push_back(0);
            }
            for(int i=2; i<=7; i++) for(int k=1; k<i; k++){
                if(gcd(i,k) != 1) continue;
                bool ok = true;
                int s = 0;
                for(int p=0; p<20; p++){
                    s += k;
                    if((s>=i)!=plus1.at(p)) ok = false;
                    s %= i;
                }
                if(ok) chmin({k,i});
            }
        }
        bigint b2 = b/worst.second*worst.first;
        int bint = (b%worst.second).get().v;
        answer += b2.get();
        for(int i=1; ; i++){
            if(i*worst.second <= bint*worst.first) answer++;
            else break;
        }
        cout << answer.v << "\n";
    }
}