E1 - Make K [Easy]

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

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

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

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

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

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

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

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

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

3
3
7
60

2
4
8

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