#include<bits/stdc++.h>
using namespace std ;

int main()
{
    int q , answer , cut ;
    cin >> q ;
    vector<int> n(q) ;
    vector<int> k(q) ;
    for(int i=0; i<q; i++)
        cin >> n.at(i) >> k.at(i) ;
    for(int i=0; i<q; i++)
    {
        answer = 0 ;
        cut = 1 ;
        while(n.at(i)>0)
        {
            answer++ ;
            n.at(i) -= cut ;
            cut *= k.at(i) ;
        }
        cout << answer-1 << endl ;
    }
}