def main():
    Q = int(input())
    for _ in range(Q):
        N, K = map(int, input().split())
        if K == 1:
            print(N - 1)
        else:
            cnt = 1
            tmp = K
            while N > tmp:
                tmp *= K
                cnt += 1
            print(cnt)


if __name__ == "__main__":
    main()