#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod (998244353)
#define PI 3.14159265358979323846
#define PII pair<int,int>
#define F first
#define S second
#define N 1000010
#define pb push_back
ll n,m;
void solve() {
    cin>>n>>m;
    ll mx=1000000000/m,c=mod,c25=-1;
    vector<PII>vt;
    vt.pb({1,m-n});
    while(!vt.empty()) {
        queue<PII>q;
        for(int i=0; i<vt.size(); i++) {
            int x=vt[i].F,y=vt[i].S;
            //cout << x<<' '<<y<<'\n';
            if(y<c) {
                c=y;
                c25=x;

            }
            if(x*2<=mx) {
                q.push({x*2,(y*2)%m});
            }
            if(i==vt.size()-1&&x*5<=mx) {
                q.push({x*5,(y*5)%m});
            }
        }
        vt.clear();
        while(!q.empty()) {
            vt.pb(q.front());
            q.pop();
        }
    }
    //cout << "ans: ";
    cout << c<< ' '<<c25*m<<"\n";
}
int main() {
    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}
/*
*/