Abwords

Time limit1sMemory limit128 MB

Summary

Given N, find the minimum word length over A/B words (starting with A, length at least 2) that admits an N-step cycle of the two given transformations.

Level: Hard8 of 10
Topics: Math, Combinatorics, Brute force, Implementation
Solved: No attempts yet

Problem

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.

Input

The first line contains the integer $N$ .

Output

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.

Constraints

$2 \le N \le 100000$

Hint

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.

Examples3

Example 1
Input
```
6
```
Expected output
```
4
```
Example 2
Input
```
2
```
Expected output
```
2
```
Example 3
Input
```
9
```
Expected output
```
9
```