题目描述

Ridbit从一个整数n开始。

在一步棋中，他可以执行以下操作之一。

把n除以它的一个正因数，或者…
如果n大于1，则从n中减去1。
正除数是一个数的除数，不包括它本身。例如，1，2，4，5，10是20的正整除数，但20本身不是。

Ridbit最少要做多少次移动才能将n减为1？

输入

第一行包含一个整数t（1≤t≤1000）–测试用例的数量。

每个测试用例的唯一一行包含一个整数n（1≤n≤10^9）。

输出

对于每个测试案例，输出将n减为1所需的最小步数。

样例

input

6
1
2
3
4
6
9

output

0
1
2
2
2
3

思路

考虑奇数偶数即可。先需特判1，2，3。1则0步，2则一步，3则两步。其余偶数均只需两步，因为都可以被2整除，进行一步指令变为2后再减1变成1即可。对于奇数，先减1后变为偶数，同上，再进行两步指令，故奇数需三步。

AC代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int ans=0;
		int x;
		scanf("%d",&x);
		if(x==1||x==2||x==3) ans=x-1;
		else if(x&1) ans=3;
		else ans=2;
		cout<<ans<<endl; 
	}
	return 0;
}