#include<bits/stdc++.h>
#define int long long
using namespace std;
void fun(int x,int y)
{
    if(y==1)
    {
        cout<<"-1\n";
    }
    int z=0;
    while(x)
    {
        x=x/y;
        z++;
    }
    cout<<z<<"\n";
}
int32_t main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int x,y;
        cin>>x>>y;
        if(y==1)
        {
            cout<<"-1"<<endl;
            continue;
        }
        else
        {
            int z=0;
            while(x)
            {
                x=x/y;
                z++;
            }
            cout<<z<<endl;
        }
    }
}