#include <bits/stdc++.h>
using namespace std;
long long num, ans;
long long T, cnt, k, n, m, l, r, mid;
bool ck(int k) {
  num = 1ll, ans = 0, cnt = k * m;
  for (int cost = 0; cost <= k; cost++) {
    if (num * cost <= cnt)
      ans += num, cnt -= num * cost;
    else {
      ans += cnt / cost;
      return ans >= n ? 1 : 0;
    }
    if (ans >= n) return 1;
    num = num * (k - cost) / (cost + 1);
  }
  return 0;
}
int main() {
  scanf("%I64d", &T);
  while (T--) {
    scanf("%I64d%I64d", &n, &m);
    l = 0, r = n;
    while (l + 1 < r) {
      mid = l + r >> 1;
      if (ck(mid))
        r = mid;
      else
        l = mid;
    }
    if (ck(l))
      printf("%I64d\n", l);
    else
      printf("%I64d\n", r);
  }
  return 0;
}
