#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>

using ll = long long;

using namespace std;

int main() {
    int q; cin >> q;
    while (q--) {
        long n, k;
        cin >> n >> k;
        if (k == 1) {
            cout << n-1 << '\n';
            continue;
        }
        long d = -1, pow = 1;
        while (n > 0) { n -= pow; pow *= k; d++; }
        cout << d << '\n';
    }
    return 0;
}