Ridbit начинает с целого числа \(n\).
За одну операцию он может выполнить одну из следующих операций:
Собственным делителем числа называется любой делитель числа, кроме самого числа. Например, \(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\).
Для наборов входных данных тестового примера \(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\)
6 1 2 3 4 6 9
0 1 2 2 2 3
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач