mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    for _ in range(int(input())):
        N, K = map(int, input().split())
        if K == 1:
            print(N-1)
            continue

        num = 0
        for i in range(35):
            num += K ** i
            if num >= N:
                ans = i
                break
        print(ans)


if __name__ == '__main__':
    main()