# Arup Guha
# 7/18/2023
# Alternate Solution to SI@UCF CP Contest #5 Problem: Spreading Competitive Programming
# Written to verify no overflow in Java solution.

# Runs a binary search on target t in y years.
def bs(t,y):

    # These are safe bounds since y>1.
    low = 0
    high = 1000000000

    # Regular binary search.
    while low < high:

        # Go halfway.
        mid = (low+high)//2

        # Real answer can't be more than mid.
        if canDo(t,y,mid):
            high = mid

        # Real anser must be at least mid+1.
        else:
            low = mid+1

    return low

# Returns true iff we can achieve a target of t in y years starting with
# teaching s students.
def canDo(t,y,s):

    # Only I know CP!
    cur = 1
    total = 1

    # Simulate each year.
    for i in range(y):

        # New students this year.
        cur *= s

        # Update total.
        total += cur

        # We did it.
        if total >= t:
            return True

        # What next year's batch will teach.
        s -= 1

        # No more teaching going on.
        if s <= 0:
            break

    # Never made it.
    return False

# Wrapper function to solve the query.
def solve(t,y):

    # Get these easy cases out of the way.
    if y == 1:
        return t-1

    # 20 is sufficient to get to the max of 10 to the 18th...
    if y > 20:
        y = 20

    # Run it.
    return bs(t,y)

# Processes cases.
def main():
    nC = int(input().strip())
    for loop in range(nC):
        t,y = map(int,input().split())
        print(solve(t,y))

# Go!
main()