#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#define ll long long

using namespace std;

ll n,m,k,t,x,ans;

ll count(int X)

{

    ll tot=;

    while (X) tot+=X%m,X/=m;

    return tot;

}

ll Min(ll A1,ll A2) { return A1<=A2?A1:A2; }

int main()

{

    cin>>t;

    while (t--)

    {

        cin>>n>>m;

        ans=~0u>>;

        for (int i=; i<=; i++)

        {

            k=sqrt(1.0*(i*i+*n));

            if (k*k!=i*i+*n) continue;

            x=k-i;

            if (x&) continue;

            x>>=;

            if (count(x)==i) ans=Min(ans,x);

        }

        if (ans==(~0U>>)) cout<<"-1\n";

            else cout<<ans<<endl;

    }

    return ;

}