A. Вычитать или делить
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ridbit начинает с целого числа $$$n$$$.

За одну операцию он может выполнить одну из следующих операций:

  • разделить $$$n$$$ на один из его собственных делителей, или
  • вычесть $$$1$$$ из $$$n$$$, если $$$n$$$ больше $$$1$$$.

Собственным делителем числа называется любой делитель числа, кроме самого числа. Например, $$$1$$$, $$$2$$$, $$$4$$$, $$$5$$$ и $$$10$$$ — это собственные делители $$$20$$$, но само число $$$20$$$ им не является.

Какое минимальное количество операций понадобится Ridbit, чтобы превратить $$$n$$$ в $$$1$$$?

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

В единственной строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$1 \leq n \leq 10^9$$$).

Выходные данные

Для каждого набора входных данных выведите минимальное необходимое число операций для превращения $$$n$$$ в $$$1$$$.

Пример
Входные данные
6
1
2
3
4
6
9
Выходные данные
0
1
2
2
2
3
Примечание

Для наборов входных данных тестового примера $$$n$$$ может быть превращено в $$$1$$$, используя следующие операции:

$$$1$$$

$$$2 \xrightarrow{} 1$$$

$$$3 \xrightarrow{} 2 \xrightarrow{} 1$$$

$$$4 \xrightarrow{} 2 \xrightarrow{} 1$$$

$$$6 \xrightarrow{} 2 \xrightarrow{} 1$$$

$$$9 \xrightarrow{} 3 \xrightarrow{} 2\xrightarrow{} 1$$$