#include <iostream>
using namespace std;
int Pabs(int *arr, int i){
int cnt = 1;
while (arr[i + 1] / arr[i] > 1){
if (arr[i + 1] % arr[i])
return 0;
cnt += 1;
arr[i + 1] /= arr[i];
}
return cnt;
}
int main() {
int n;
cin >> n;
int arr[n * 2];
for (int i = 0; i < n * 2; ++i)
cin >> arr[i];
for (int i = 0; i < n * 2; i += 2)
cout << Pabs(arr, i) << endl;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBQYWJzKGludCAqYXJyLCBpbnQgaSl7CglpbnQgY250ID0gMTsKCXdoaWxlIChhcnJbaSArIDFdIC8gYXJyW2ldID4gMSl7CgkJaWYgKGFycltpICsgMV0gJSBhcnJbaV0pCgkJCXJldHVybiAwOwoJCWNudCArPSAxOwoJCWFycltpICsgMV0gLz0gYXJyW2ldOwoJfQoJcmV0dXJuIGNudDsKfQoKaW50IG1haW4oKSB7CglpbnQgbjsKCWNpbiA+PiBuOwoJaW50IGFycltuICogMl07Cglmb3IgKGludCBpID0gMDsgaSA8IG4gKiAyOyArK2kpCgkJY2luID4+IGFycltpXTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbiAqIDI7IGkgKz0gMikKCQljb3V0IDw8IFBhYnMoYXJyLCBpKSA8PCBlbmRsOwp9