import java.util.*;

/**
 * If we have d days remaining and k sites, then we can distinguish at most 
 * (d+1)^k compounds.
 *
 * Define 
 *  g(d,k)=\Sum_{i=0}^k g(d-1,k-i)*(k choose i)
 * The intuition for this is:
 *  On each day we can choose a number of sites to "use" and a number of 
 *  compounds to group there. Using i sites means that we will have k-i 
 *  sites remaining on the next day. We can group as many compounds there 
 *  as the largest number that we could distinguish with k-i sites and d-1
 *  days. There are (k choose i) many ways to "use" i sites. 
 *
 * Just compute (d+1)^k for each possible value of k until (d+1)^k >= n.
 *
 * @author Finn Lidbetter
 */

public class allergen_testing_finn {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int q=0; q<t; q++) {
            long n = sc.nextLong();
            long d = sc.nextLong();
            long ans = -1;
            if (n==1) {
                ans = 0;
            }
            else {
                long upper = 1;
                for (int i=1; i<=60; i++) {
                    if (upper*(d+1) >= n || upper > (Long.MAX_VALUE / (d+1))) {
                        ans = i;
                        break;
                    }
                    upper *= (d+1);
                }
            }
            System.out.println(ans);
        }
    }
}