题目描述

小博从一个整数$n$开始。

在一次移动中，他可以执行以下操作之一：

1. 将$n$除以其一个"proper"因子
2. 如果$n$大于$1$，则将$n$减$1$

正整数$n$的"proper"因子是指除自身以外的因子。例如，20的"proper"因子是$1、2、4、5$和$10$，但$20$本身不是。

小博需要进行的最少移动次数是多少，才能将$n$减小为$1$?

输入格式

第一行包含一个整数$t$表示测试用例的数量。

每个测试用例的唯一一行包含一个整数$n$

输出格式

对于每个测试用例，输出将$n$减小为$1$所需的最少移动次数。

样例输入

6
1
2
3
4
6
9

输出数据

0
1
2
2
2
3

数据范围

对于$30\%$ 的数据，$t=1,1 \leq n \leq 1000$

对于$60\%$的数据，$2 \leq t \leq 20,1 \leq n \leq 10^5$

对于$100\%$的数据，$2 \leq t \leq 1000,1 \leq n \leq 10^9$

样例解释

$n$可以通过以下操作序列将其减小到$1$：

1

2->1

3->2->1

4->2->1

6->2->1

9->3->2->1