for _ in range(int(input())):
    N, K = map(int, input().split())

    if K == 1:
        print(N-1)
    else:
        SUM = 1
        cnt = 0
        while SUM < N:
            cnt += 1
            SUM += K**cnt
        print(cnt)