#include<iostream>

using namespace std;

int CountOf(int n){
    int count=0,div=2;
    while(n!=1){
        while(n%div) div++;
        count++;
        n/=div;
    }
    return count+1;
}
void main()
{
    short T;
    cin>>T;
    int i,*A,*B;
    A=new int[T];
    B=new int[T];
    for(i=0;i<T;i++){
        cin>>A[i]>>B[i];
    }
    for(i=0;i<T;i++)
    {
        if(A[i]==0) cout<<0<<endl;
        else cout<<((A[i]>B[i] || B[i]%A[i]) ? 0:CountOf(B[i]/A[i]))<<endl;
    }
}