P2618 Number Engineering

The ACM Laboratory has launched a number engineering project, aiming to transform a positive integer $n$ into $1$ using some special methods. Available methods are: 1. Subtract $1$. 2. Divide by any one of its prime factors. Each operation consumes one unit of energy. What is the minimum energy required to turn $n$ into $1$?

This problem contains multiple test cases. For each test case, there is one line with an integer $n$.

Output one line with a single integer, the minimum energy consumed.

Constraints: $1 \le n \le 10^6$. Translated by ChatGPT 5