// Problem: H. Shiori Miyagi and Maximum Array Score
// Contest: Codeforces - Codeforces Round 1065 (Div. 3)
// URL: https://codeforces.com/contest/2171/problem/H
// Memory Limit: 256 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

namespace rngs = std::ranges;
using ll = long long;
using a2l = array<ll, 2>;
using vl = vector<ll>;

void solve()
{
ll n, m;
cin >> n >> m;

vector<map<ll, ll>> cache(n + 1);
auto dfs = [&](auto &&self, ll id, ll v) -> ll {
if (cache[id].count(v))
return cache[id][v];
assert(id >= 2);
if (id == 2)
return cache[id][v] = std::__lg(v - 1);
ll ret = 0;

for (ll nv = 1, gain = 0; nv < v; nv *= id, gain += 1)
ret = max(ret, self(self, id - 1, nv) + gain);

return cache[id][v] = ret;
};

auto ans = dfs(dfs, n, m + 1);
cout << ans << '\n';
}

int main(int argc, char **argv)
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

ll t = 1;
cin >> t;
while (t--)
solve();

return 0;
};