RT，__int128 操作已省：

#include<bits/stdc++.h>
using namespace std;
#define ll __int128
ll pow(ll a, ll b, ll p) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return ans;
}
ll inv(ll a, ll p) {
    return pow(a, p-2, p);
}
double Sqrt(ll x){     
    if(x <= 0) return 0;  
    double begin = 1;  
    double end = x/2+1;  
    double mid, lastmid;  
    mid = begin + (end-begin)/2;  
    do{  
        if(mid < x/mid) begin = mid;  
        else end = mid;  
        lastmid = mid;  
        mid = begin + (end-begin)/2;  
    }  
    while(abs(lastmid-mid) > FLT_MIN);  
    return mid;  
}  
map<ll, ll>mp;
ll bsgs(ll A, ll B, ll C) {
    mp.clear();
    if(A % C == 0) return -2;
    ll m = ceil(Sqrt(C));
    ll ans;
    for(int i = 0; i <= m; i++) {
        if(i == 0) {
            ans = B % C;
            mp[ans] = i;
            continue;
        }
        ans = (ans * A) % C;
        mp[ans] = i;
    }
    ll t = pow(A, m, C); 
    ans = t;
    for(int i = 1; i <= m; i++) {
        if(i != 1)ans = ans * t % C;
        if(mp.count(ans)) {
            int ret = i * m % C - mp[ans] % C;
            return (ret % C + C)%C;
        }
    }
    return -2;
}
ll k, m ,n;
signed main(){
    cin >> k >> m;
    k = k * 9 + 1;
    k %= m;
    ll ans = bsgs(10, k, m);
    cout << ans;
}