#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
bool check(int mid) {
  ll cnt = m * 1ll * mid, C = 1, ret = 1;
  for (int i = 1; i <= mid && cnt; i++) {
    C = C * (mid - i + 1) / i;
    if (cnt >= C * i)
      cnt -= C * i, ret += C;
    else {
      ret += cnt / i;
      break;
    }
    if (ret >= n) return 1;
  }
  return ret >= n;
}
int main() {
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    cin >> n >> m;
    int l = 0, r = n, ans = -1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (check(mid))
        ans = mid, r = mid - 1;
      else
        l = mid + 1;
    }
    cout << ans << endl;
  }
  return 0;
}
