Abwords

A word is a string of two or more letters, each of them A or B, that starts with A. Two actions can be applied to a word, and each one gives another word.

• R1: change only the last letter. A becomes B and B becomes A. Every other letter stays as it is.
• R2: build a new word $t$ from the word $w$. The first letter of $t$ is A. At a position $i > 1$, the letter $t_i$ is B when $w_{i-1}$ and $w_i$ are equal, and A when they differ. The new word $t$ then replaces $w$.

Start from a word $w$ and apply $N$ actions of type R1 and R2 in any order. The sequence of actions is an $N$-transformation of $w$ when both of these hold.

• The word after the $N$-th action equals $w$.
• The $N-1$ words produced along the way differ from one another and from $w$.

An integer $N$ greater than 1 is given. Find the smallest number of letters a word can have if it starts an $N$-transformation.

The first line contains the integer $N$.

Print on one line the smallest number of letters of a word that can start an $N$-transformation. If no such word exists, print -1.

• $2 \le N \le 100000$

No word of fewer than 4 letters starts a sequence of 6 actions that comes back to it without any word appearing twice along the way. The four-letter word AABB does have such a sequence. Applying R2 to AABB gives ABAB, another R2 gives AAAA, R1 gives AAAB, R2 gives ABBA, R1 gives ABBB, and a last R2 comes back to AABB. So the answer for $N = 6$ is 4.