MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    q = int(input())
    for _ in range(q):
        n,k = map(int,input().split())
        if k == 1:
            print(n - 1)
        else:
            ans = 1
            cnt = k + 1
            leaf = k
            while cnt < n:
                cnt += leaf * k
                leaf *= k
                ans += 1
            print(ans)


if __name__ =='__main__':
    main()