#include<iostream>
#include<algorithm>
#include<stack>
#include<set>
#include<unordered_set>
#include<queue>
#include<deque>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<map>
#include<string>
#include<vector>
#include<array>
#include<functional>
using namespace std;
typedef long long ll;
ll highbit(ll x){
    ll ans=2;
    int num=1;
    while(x){
        x>>=2;
        ans<<=2;
        num++;
    }
    return num;
}
ll lowbit(ll x){
    return x&(-x);
}
long long max(long long a,long long b){
    return a>b?a:b;
}
long long min(long long a,long long b){
    return a>b?b:a;
}
ll gcd(ll x,ll y)
{
    if(y==1)
        return x;
    return gcd(y,x%y);
}
const int maxn=100;
ll lg10[20];
struct num{
    ll lg,x;
    ll pos;
    bool flag;
    bool operator<(num&that){
        if(this->x==0){
            return true;
        }
        if(that.x==0){
            return false;
        }
        if(abs(this->lg-that.lg)>9){
            return this->lg<that.lg;
        }else{
            ll diff=abs(this->lg-that.lg);
            ll x1,x2;
            x1=this->x;
            x2=that.x;
            if(this->lg<that.lg){
                x2*=lg10[diff];
            }else{
                x1*=lg10[diff];
            }
            if(x1==x2){
                return this->pos>that.pos;
            }else{
                return x1<x2;
            }
        }
    }
};
void add1(string& now){
    now[0]++;
    int pos=0;
    while(now[pos]-'0'>=10){
        now[pos+1]++;
        now[pos]=('0'+(now[pos]-'0')%10);
        pos++;
    }
}
string mul(string& k,ll m){
    string ans;
    ll buff=0;
    for(int i=0;i<k.size();i++){
        ll x=k[i]-'0';
        x*=m;
        x+=buff;
        ans.push_back(x%10+'0');
        buff=x/10;
    }
    while(buff){
        ans.push_back(buff%10);
        buff/=10;
    }
    ans.push_back('0');
    return ans;
}
array<ll,2> ston(string& a,string& sm){
    ll an=0,smn=0;
    for(int i=0;i<a.size();i++){
        an+=(a[i]-'0')*lg10[i];
    }
    for(int i=0;i<sm.size();i++){
        smn+=(sm[i]-'0')*lg10[i];
    }
    array<ll,2> ans;
    ans[0]=an;
    ans[1]=smn;
    return ans;
}
bool cmp(string& a,string& b){
    int na=a.size();
    int nb=b.size();
    while(na<nb){
        a.push_back('0');
        na++;
    }
    while(nb<na){
        b.push_back('0');
        nb++;
    }
    int n=a.size();
    for(int i=n-1;i>=0;i--){
        if(a[i]==b[i]){
            continue;
        }else{
            return a[i]<b[i];
        }
    }
    return true;
}
void clear(string&a){
    while(!a.empty()&&a[a.size()-1]=='0'){
        a.pop_back();
    }
}
void solve() {
    ll m;
    string n;
    cin>>n;
    reverse(n.begin(),n.end());
    add1(n);
    cin>>m;
    ll nk=0;
    lg10[0]=1;
    for(int i=1;i<20;i++){
        lg10[i]=lg10[i-1]*10;
    }
    ll buff=0;
    string ans;
    string sm;
    reverse(n.begin(),n.end());
    for(int i=0;i<n.size();i++){
        buff*=10;
        buff+=(n[i]-'0');
        ans.push_back(('0'+buff/m));
        buff=buff%m;
    }
    reverse(ans.begin(),ans.end());
    ans.push_back('0');
    reverse(n.begin(),n.end());
    n.push_back('0');
    if(buff>0){
        add1(ans);
    }
    //add1(n);
    string m1=mul(ans,m);
    string m2;
    while(m){
        sm.push_back(m%10+'0');
        m/=10;
    }
    vector<num> arr;
    int len=sm.size();
    vector<int> st;
    for(int i=len-1;i<n.size();i++){
        string pre;
        for(int j=i-len+1;j<=i;j++){
            pre.push_back(n[j]);
        }
        array<ll,2> nk=ston(pre,sm);
        if(nk[1]==nk[0]){
            st.push_back(1);
            break;
        }
        if(nk[1]<nk[0]&&i!=n.size()-2){
            continue;
        }
        if(nk[1]<nk[0]&&i==n.size()-2){
            string bk=sm;
            bk.push_back('1');
            nk=ston(pre,bk);
            num now;
            now.pos=i+1;
            now.x=nk[1]-nk[0];
            now.lg=i-len+1;
            now.flag=true;
            arr.push_back(now);
            continue;
        }
        num now;
        now.pos=i;
        now.x=nk[1]-nk[0];
        now.lg=i-len+1;
        now.flag=false;
        arr.push_back(now);
    }
    sort(arr.begin(),arr.end());
    if(arr.size()>0||st.size()>0){
        if(st.size()==0){
            int pos=arr[0].pos;
            if(arr[0].flag){
                n[pos]='1';
                pos--;
            }
            int nk=0;
            for(int j=pos-len+1;j<=pos;j++){
                n[j]=sm[nk];
                nk++;
            }
            for(int i=0;i<pos-len+1;i++){
                n[i]='0';
            }
        }
        if(cmp(m1,n)){
            clear(m1);
            reverse(m1.begin(),m1.end());
            cout<<m1<<endl;
        }else{
            clear(n);
            reverse(n.begin(),n.end());
            cout<<n<<endl;
        }
    }else{
        clear(m1);
        reverse(m1.begin(),m1.end());
        cout<<m1<<endl;
    }
}
int main(void){
    unsigned int t;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    cin>>t;
    //t=1;
    while(t--){
        solve();
    }
    return 0;
}