import sys
input = sys.stdin.readline

Q=int(input())

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

    if K==1:
        print(N-1)
        continue

    node=1
    depth=1

    while node<N:
        node+=K**depth
        depth+=1

    print(depth-1)