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

int main() {
	long long Q;
	cin >> Q;
	for (int q = 0; q < Q; q++) {
		long long N, K;
		cin >> N >> K;
		if (K == 1) {
			cout << N - 1 << endl;
			continue;
		}
		long long NOW = 1, COUNT = 1, ANS = 0;
		while (COUNT < N) {
			COUNT += NOW;
			ANS++;
			NOW *= K;
		}
		cout << ANS << endl;
	}
}