题目描述

给你一个整数 $x$，你每次可以进行下面 $3$ 种操作中的一种。

• 如果存在一个整数 $d$（$1\lt d \lt x$），使得 $d\mid x$，就可以把 $x$ 变为 $d$。
• 把 $x$ 减 $1$。
• 把 $x$ 减 $2$。

请问你最少需要多少次操作可以把 $x$ 变为 $1$。

输入格式

第一行一个正整数 $T$（$1\le T \le 10^4$），代表测试样例的组数。

接下来的 $T$ 行，每行 $1$ 个正整数 $x$（$1\le x \le 10^9$）。

输出格式

输出 $T$ 行，每行一个正整数表示最少操作次数。

输入样例

4
1
2
3
9

输出样例

0
1
1
2

提示

对于样例 $2$：直接减 $1$

对于样例 $4$：一种可能的操作是 $9\rightarrow 3 \rightarrow1$