Description

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$?

Input Format

This problem contains multiple test cases.

For each test case, there is one line with an integer $n$.

Output Format

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

1
4

0
2

Hint

Constraints: $1 \le n \le 10^6$.

Translated by ChatGPT 5