#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
int t;
void read() { cin >> t; }
int n, m;
bool can(int x) {
  long long sum = 0;
  int temp = n;
  for (int i = 0; i <= x && temp; i++) {
    long long c = 1;
    int curr = 1;
    for (int j = x - i + 1; j <= x; j++) {
      c *= j;
      while (curr <= i && c % curr == 0) {
        c /= curr;
        curr++;
      }
      if (curr >= i && c >= temp) break;
    }
    sum += 1ll * min((long long)temp, c) * i;
    temp -= min((long long)temp, c);
    if (sum > 1ll * x * m) return false;
  }
  return !temp && sum <= 1ll * x * m;
}
void solve() {
  while (t--) {
    cin >> n >> m;
    int low = 0, high = n;
    while (low < high) {
      int mid = (low + high) / 2;
      if (can(mid))
        high = mid;
      else
        low = mid + 1;
    }
    cout << low << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  read();
  solve();
}
