def main():
    for _ in range(int(input())):
        n,k=map(int,input().split())
        if k==1:
            print(n-1)
        else:
            for i in range(100):
                if pow(k,i)>=n:
                    print(i)
                    break
main()