if __name__=='__main__':
    for _ in range(int(input())):
        n, k = map(int, input().split())
        if k==1:
            print(n-1)
            continue
        ans = 0
        n -= 1
        t = k
        while n>0:
            n -= t
            t *= k
            ans += 1
        print(ans)