题目描述

育华开启了一个数字工程项目，希望把正整数 $n$ 通过一些特殊方法变成 $1$。

可采用的方法有：

1. 减去 $1$
2. 除以它的任意一个素因子。

每操作一次消耗一个单位的能量。

请问把 $n$ 变成 $1$ 最少需要消耗多少能量？

输入格式

本题有多组数据。 第一行 一个整数 $T$，表示数据组数。 对于每组测试，一行一个整数 $n$。

输出格式

一行一个整数，表示最少消耗的能量。

样例 #1

样例输入 #1

2
1
4

样例输出 #1

0
2

提示

$1 \le n \le 10^6$。