問題 E2 とは制約のみが異なります

問題文

あなたは整数 $x$ を持っており，はじめ $x = 1$ です．

また，以下の操作を繰り返し行うことができます.

• $x$ を，次の $\mathrm{A}, \mathrm{B}$ の値のうちのいずれか一方で置き換える
  • $\mathrm{A}\colon x + 1$
  • $\mathrm{B}\colon x$ の正の約数の総和

$T$ 個のテストケースが与えられます．
$t \scriptsize \hspace{0.3em} (1 \leq t \leq T)$ 個目のテストケースでは，$K=K_t$ として次の問題を解いてください．

• $x$ を $K$ に等しくするために必要な操作回数の最小値を求めよ．
• なお，この問題の制約下において，必ず $x$ を $K$ に一致させることができる．

制約

• $1 \leq T \leq 10^4$
• $2 \leq K_t \leq 7 \times10^4 \hspace{0.3em} \scriptsize (1 \leq t \leq T)$
• 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

出力

$T$ 行出力せよ．
$t \scriptsize \hspace{0.3em} (1 \leq t \leq T)$ 行目には $t$ 個目のテストケースに対する答えを出力せよ．

サンプル

3
3
7
60

2
4
8

たとえば $\mathrm{A}$ を $2$ 度選んで操作を行うと $x$ を $1 \to 2 \to 3$ と $2$ 回の操作で $3$ に一致させることができます．
また，選ぶ値を適切に決めると $x$ を $1 \to 2 \to 3 \to 4 \to 7$ と $4$ 回の操作で $7$ に一致させることができます．
これらが最小です．