#include using namespace std; using ll = long long; using Graph = vector>; int main() { int Q; cin >> Q; vector> NK(Q); for(int i = 0; i < Q; i++) { int a,b; cin >>a >> b; NK[i] = {a,b}; } for(int i = 0; i < Q; i++) { int x = NK[i].first; int y = NK[i].second; if(y == 1) { cout << x- 1 << endl; continue; } int ans = 0; while(true) { if(x == 0) break; x /= y; ans++; } cout <