import sys


def input(): return sys.stdin.readline().rstrip('\n')


def main():
    q = int(input())
    for _ in range(q):
        n, k = map(int, input().split())
        if k == 1:
            print(n-1)
        else:
            d = 1
            a = -1
            while n > 0:
                n -= d
                a += 1
                d *= k
            print(a)


if __name__ == '__main__':
    main()