import math


def main():
    q = int(input())
    for i in range(q):
        n, k = map(int, input().split())
        if k == 1:
            print(n - 1)
        else:
            print(math.floor(math.log(n * (k - 1) + 1, k)))


if __name__ == "__main__":
    main()