D. Штурм Арасаки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ха, ты только что озвучил, как становятся легендой.
— Cyberpunk 2077
Вы с Джонни Сильверхендом решили вдвоём штурмовать Арасаку. Пройдя через охрану, вы добрались до Микоши — но, чтобы подключиться к ней, нужно взломать главный сервер.

Пароль к серверу формируется так. Есть секретное число $$$n$$$. Рассмотрим все его положительные делители, кроме $$$1$$$, но делитель равный $$$\mathbf{n}$$$ рассматривается, и разобьём их всех на несколько непустых слоёв $$$L_1, L_2, \ldots, L_k$$$. Разбиение называется хорошим, если выполняются два условия:

  • для любого делителя $$$x$$$ из слоя $$$L_i$$$ все его делители, кроме $$$1$$$ и $$$x$$$, лежат только в слоях $$$L_1, L_2, \ldots, L_{i-1}$$$;
  • в каждом слое можно упорядочить все числа в цепочку так, чтобы любые два соседних числа в этой цепочке имели НОД$$$^{\text{∗}}$$$ больше $$$1$$$.

Длиной пароля считается количество слоёв $$$k$$$. Для безопасности слоёв их должно быть как можно меньше.

К счастью, Арасака не меняла $$$n$$$ со времён Джонни, а он помнит несколько вариантов этого числа. Для каждого из них помогите Ви и Джонни определить минимальное возможное количество слоёв.

$$$^{\text{∗}}$$$$$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В единственной строке каждого набора содержится целое число $$$n$$$ ($$$2 \le n \le 10^6$$$) — вариант секретного числа, который назвал Джонни.

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

Для каждого набора входных данных выведите одно число — минимальное количество слоёв.

Пример
Входные данные
8
2
4
8
16
32
67
120
33
Выходные данные
1
2
3
4
5
1
7
3
Примечание

В первых $$$5$$$ наборах входных данных дано число вида $$$2^k$$$, покажем, что ответ для них равен $$$k$$$. Рассмотрим все положительные делители, кроме $$$1$$$: $$$2^1, 2^2, \ldots, 2^{k}$$$. Видно, что никакие два не могут лежать в одном слое, а значит, все они лежат в разных слоях. Пример расположения: $$$L_i = \{2^i\}$$$. Видно, что оно удовлетворяет условиям, и получится ровно $$$k$$$ слоёв.