// Arup Guha
// 7/18/2023
// Solution to SI@UCF CP Camp Contest #5 Problem: Teaching Competitive Programming

import java.util.*;

public class teaching {

	public static void main(String[] args) {
	
		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();
		
		// Process cases.
		for (int loop=0; loop<nC; loop++) {
			long t = stdin.nextLong();
			long y = stdin.nextLong();
			System.out.println(solve(t,y));
		}
	}
	
	public static long solve(long t, long y) {
	
		// Get this easy case out of the way.
		if (y == 1) return t-1;
		
		// This is key to reduce overflow.
		if (y > 20) y = 20;
		
		return bs(t, y);
	}
	
	public static long bs(long t, long y) {
	
		// These should be safe because I have safeguards in my canDo method.
		// Note low = 0, this will only occur when t = 1. You can if statement this out also.
		long low = 0, high = 1000000000;
		
		while (low < high) {
		
			long mid = (low+high)/2;
			
			// mid is good enough. answer is no bigger than mid.
			if (canDo(t, y, mid))
				high = mid;
				
			// mid doesn't work so it's atleast mid+1.
			else
				low = mid+1;
		}
		
		// Ta da!
		return low;
	}
	
	public static boolean canDo(long t, long y, long s) {
	
		// Year zero.
		long cur = 1;
		long total = 1;
		
		// Simulate each year.
		for (int i=0; i<y; i++) {
			
			// To avoid overflow.
			if (Math.log10(cur) + Math.log10(s) > 18) return true;
			
			// New students taught.
			cur *= s;
			
			// Add to total.
			total += cur;
			
			// We're good.
			if (total >= t) return true;
			
			// Less charismatic teachers next year.
			s--;
			
			// Be safe!
			if (s <= 0) break;
		}
		
		// Never made it.
		return false;
	}
}