Reduce Number to One

ACM Lab has initiated a digital engineering project that involves transforming a positive integer \(n\) into \(1\) using special operations. You are allowed to perform the following two operations:

1. Subtract \(1\) from \(n\).
2. Divide \(n\) by any one of its prime factors.

Each operation consumes 1 unit of energy. Your task is to determine the minimum energy required to reduce \(n\) to \(1\).

inputFormat

The input consists of a single positive integer \(n\) (\(n \ge 1\)).

outputFormat

Output a single integer representing the minimum energy required to transform \(n\) into \(1\).

sample

1

0