#include <bits/stdc++.h>
using namespace std;
int T, l, r, n, m, i;
long long num, y, x, k, mid;
int main() {
  for (scanf("%d", &T); T--;) {
    scanf("%d%d", &n, &m);
    l = 0;
    r = n;
    while (l <= r) {
      mid = (l + r) / 2;
      k = mid * m;
      x = 1;
      y = n;
      for (i = 0; i <= mid && k >= 0 && y; ++i) {
        num = min(y, x);
        y -= num;
        k -= num * i;
        x = x * (mid - i) / (i + 1);
      }
      if (k >= 0 && !y)
        r = mid - 1;
      else
        l = mid + 1;
    }
    printf("%d\n", r + 1);
  }
}
