#include <bits/stdc++.h>
using namespace std;
int main() {
float t,n,k;
cin >> t;
while(t--){
cin >> n >> k;
float x = 1;
if(n < k || k == 1){
cout << n << endl;
}else{
int in = k;
while(n > pow(k,x)){
x++;
}
cout << n << " " << pow(k,x-1) << endl;
}
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CiAgICBmbG9hdCB0LG4sazsKICAgIGNpbiA+PiB0OwogICAgd2hpbGUodC0tKXsKICAgIAljaW4gPj4gbiA+PiBrOwogICAgCWZsb2F0IHggPSAxOwogICAgCWlmKG4gPCBrIHx8IGsgPT0gMSl7CiAgICAJCWNvdXQgPDwgbiA8PCBlbmRsOwogICAgCX1lbHNlewogICAgCQlpbnQgaW4gPSBrOwogICAgCQl3aGlsZShuID4gcG93KGsseCkpewogICAgCQkJeCsrOwogICAgCQl9CiAgICAJCWNvdXQgPDwgbiA8PCAiICIgPDwgcG93KGsseC0xKSA8PCBlbmRsOwogICAgCX0KICAgIH0KICAgIHJldHVybiAwOwp9Cg==