1243. Yet Another Race to 1 Problem

给定一个数 xx，你每次可以做如下 33 种操作:

  • 如果存在一个整数 d(1<d<x)d(1 < d < x)，使得 dd 整除 xx，把 xx 变成 dd。
  • 把 xx 减 11。
  • 把 xx 减 22。

请问，最少多少步可以把 xx 变成 11。

输入

第一行一个数 TT，表示测试的组数。(1≤T≤2000)(1 ≤ T ≤ 2000)

每组一个正整数 x (0<x≤1000000000)x \ (0 < x ≤ 1000000000)，含义如题意所示

输出

对于每组测试，输出一行，表示 xx 最少要经过多少步上述操作得到 11。

样例

标准输入 复制文本 
3
12
2
1
标准输出 复制文本 
2
1
0

来源

2019 SCNUCS-N 现场赛

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 33
通过 9

上一题 1242 下一题 1244