Defeat the Monster

You are given a monster with a health value \(h\). The monster is defeated only when its health is exactly 0. You have two types of attacks:

• Physical Attack: On the \(i\)-th physical attack, you deal \(2^{i-1}\) damage.
• Magic Attack: You may choose any prime number \(x\) (with \(x \le h'\), where \(h'\) is the current health of the monster) and deal \(x\) damage. However, you can use a magic attack at most once.

Your task is to determine whether you can defeat the monster and, if so, compute the minimum number of attacks required. Note that the attacks (physical and magic) can be performed in any order. In other words, you need to find nonnegative integer \(k\) (number of physical attacks) and decide whether to use a magic attack (at most one) such that:

[ \text{Total Damage} = \Bigl(2^k - 1\Bigr) + \begin{cases}0, & \text{if no magic attack is used}\ p, & \text{if magic attack is used (with } p \text{ prime)} \end{cases} = h. ]

If there is no valid sequence of attacks that exactly reduces the monster's health to 0, output -1.

inputFormat

The input consists of a single integer \(h\) representing the health of the monster.

h

outputFormat

Output the minimum number of attacks required to defeat the monster. If it is not possible, output -1.

sample

1

1