#include <iostream>
using namespace std;
int main(){
	int Q;
	cin >> Q;
	for (int i = 0; i < Q; i++){
		int N, K;
		cin >> N >> K;
		if (K == 1){
			cout << N -  1 << endl;
		} else {
			long long s = 1;
			long long c = 1;
			int d = 0;
			while (1){
				if (s >= N){
					cout << d << endl;
					break;
				}
				c *= K;
				s += c;
				d++;
			}
		}
	}
}