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

#define REP(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

typedef long long ll;

int main(void){
	int q;
	cin >> q;

	ll n, k, l;
	REP(i, q){
		cin >> n >> k;
		l = k; n--;
		int cnt = 0;
		if(k == 1){
			cout << n << endl;
			continue;
		}
		while(1){
			if(n <= 0) break;
			cnt++;
			n -= l;
			l *= k;
		}
		cout << cnt << endl;
	}

	return 0;
}