#include <bits/stdc++.h>
using namespace std;
const int N=32;
const long long inf=1e9;
long long A[N][N],C,D;
void exgcd(long long a,long long b,long long &x,long long &y){
  if(!b){
    x=1,y=0; return;
  }
  exgcd(b,a%b,y,x);
  y-=(a/b)*x;
}
void solve(){
  int a,b,t;
  cin>>a>>b,t=b;
  int k=b;
  while(k%2==0) k/=2;
  while(k%5==0) k/=5;
  if(k==1){
    cout<<0<<" "<<1<<'\n'; return;
  }
  C=1e18,D=0;
  for(int i=0;i<=30;i++)
    for(int j=0;j<=30;j++){
      if(A[i][j]*k>inf||A[i][j]*k<0) break;
      int x1=A[i][j]%k*a%k;
      int x2=t/k;
      int res=k-x1;
      long long Y,Z;
      exgcd((x2)%k,k,Y,Z);
      // if(i==0&&j==0)
      // cout<<k<<"ssss"<<","<<Y<<","<<res<<","<<Z<<endl;
      Y=(Y%k+k)%k;
      Y=Y*res%k;
      if(C>Y){
        C=Y,D=A[i][j]*k;
      }
    }
  cout<<C<<" "<<D<<'\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int T; cin>>T;
  A[0][0]=1;
  for(int i=0;i<=30;i++)
    for(int j=0;j<=30;j++){
      if(i+j==0) continue;
      if(i>=1) A[i][j]=A[i-1][j]*2;
      else A[i][j]=A[i][j-1]*2;
      if(A[i][j]<0||A[i][j]>inf) A[i][j]=-1;
    }
  while(T--) solve();
}
// 4
// 1 2
// 2 3
// 3 7
// 19 79