//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <iterator>
#include <unordered_map>
#include <unordered_set>
#include <tuple> 
#include <random>
#include <cassert>
using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(long long i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)

using Weight = int;
using Flow = int;
struct Edge {
    int src, dst;
    Weight weight;
    Flow cap;
    Edge() : src(0), dst(0), weight(0) {}
    Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;

void add_edge(Graph &g, int a, int b, Weight w = 1) {
    g[a].emplace_back(a, b, w);
    g[b].emplace_back(b, a, w);
}
void add_arc(Graph &g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); }

std::vector<Weight> dijkstra(const Graph &g, int s) {
    const Weight INF = std::numeric_limits<Weight>::max() / 8;
    using state = std::tuple<Weight, int>;
    std::priority_queue<state> q;
    std::vector<Weight> dist(g.size(), INF);
    dist[s] = 0;
    q.emplace(0, s);
    while (q.size()) {
        Weight d;
        int v;
        std::tie(d, v) = q.top();
        q.pop();
        d *= -1;
        /* if(v == t) return d; */
        if (dist[v] < d) continue;
        for (auto &e : g[v]) {
            if (dist[e.dst] > dist[v] + e.weight) {
                dist[e.dst] = dist[v] + e.weight;
                q.emplace(-dist[e.dst], e.dst);
            }
        }
    }
    return dist;
}

std::vector<ll> eratosthenes_sieve(int n) {
    std::vector<ll> ps(n + 1);
    std::iota(ps.begin() + 2, ps.end(), 2);
    for (int i = 2; i * i <= n; ++i)
        if (ps[i])
            for (int j = i * i; j <= n; j += i) ps[j] = 0;
    return ps;
}

std::vector<ll> make_primes(int n) {
    std::vector<ll> ps = eratosthenes_sieve(n);
    ps.erase(std::remove(ps.begin(), ps.end(), 0), ps.end());
    return ps;
}
const int N = 100010;
int prime[N];

int main() {
    vector <ll> v = make_primes(N);
    Graph g(N + 10);
    for (int i = 1;i <= N;i++) {
        add_arc(g, i - 1, i);
        add_arc(g, i + 1, i);
        ll x = i;
        for (ll j = 0;v[j] * v[j] <= x;j++) {
            if (x%v[j] == 0) {
                add_arc(g, i / v[j], i);
                while (x%v[j] == 0)x /= v[j];
            }
        }
    }
    for (int i = 1;i <= v.size();i++) {
        add_arc(g, 1, v[i]);
    }
    vector<int> u = dijkstra(g, 1);
    int T;cin >> T;
    while (T--) {
        int a;cin >> a;
        cout << u[a] << endl;
    }
}