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

問題文


あなたは整数 を持っており,はじめ です.

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

  • を,次の の値のうちのいずれか一方で置き換える
    • の正の約数の総和

個のテストケースが与えられます.
個目のテストケースでは, として次の問題を解いてください.

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

制約


  • 入力はすべて整数である

入力


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





出力


行出力せよ.
行目には 個目のテストケースに対する答えを出力せよ.

サンプル


入力例1
3
3
7
60
出力例1
2
4
8

たとえば 度選んで操作を行うと 回の操作で に一致させることができます.
また,選ぶ値を適切に決めると 回の操作で に一致させることができます.
これらが最小です.

提出


Go (1.14)