#include <bits/stdc++.h>
using namespace std;

#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0);
#define endl "\n"
#define int long long

int32_t main()
{
    IOS;
    vector<int> dp(20000001);

    dp[1] = 0;
    for (int i = 2; i < 20000001; i++)
    {
        int x = INT_MAX, y = INT_MAX, z = INT_MAX;
        if (i % 2 == 0)
        {
            x = dp[i / 2] + 1;
        }
        if (i % 3 == 0)
        {
            y = dp[i / 3] + 1;
        }
        z = dp[i - 1] + 1;
        dp[i] = min(x, min(y, z));
    }
    int t, n;
    cin >> t;
    while (t--)
    {
        cin >> n;
        cout << dp[n] << endl;
    }

    return 0;
}