Abwords

A와 B로만 이루어지고 길이가 2 이상이며 A로 시작하는 문자열을 단어라고 한다. 단어에는 다음 두 연산을 적용할 수 있고, 그 결과도 다시 단어가 된다.

• R1: 마지막 글자만 바꾼다. A는 B가 되고 B는 A가 된다. 나머지 글자는 그대로 둔다.
• R2: 단어 $w$에서 새 단어 $t$를 만든다. $t$의 첫 글자는 A이다. $i > 1$인 자리에서는 $w_{i-1}$과 $w_i$가 같으면 $t_i$가 B, 다르면 A이다. 이렇게 만든 $t$가 $w$를 대신한다.

단어 $w$에서 시작해 R1과 R2를 원하는 순서로 $N$번 적용했을 때 다음 두 조건을 모두 만족하면, 이 연산 열을 $w$의 $N$-변환이라고 한다.

• $N$번째 연산을 마친 단어가 $w$와 같다.
• 도중에 나온 단어 $N-1$개가 서로 다르고 $w$와도 다르다.

1보다 큰 정수 $N$이 주어진다. $N$-변환을 시작할 수 있는 단어의 최소 글자 수를 구하라.

첫째 줄에 정수 $N$이 주어진다.

$N$-변환을 시작할 수 있는 단어의 최소 글자 수를 한 줄에 출력한다. 그런 단어가 없으면 -1을 출력한다.

• $2 \le N \le 100000$

6번의 연산으로 자기 자신에게 돌아오면서 도중에 같은 단어가 두 번 나오지 않는 단어 중에 글자 수가 4보다 적은 것은 없다. 반면 네 글자 단어 AABB에는 그런 연산 열이 있다. AABB에 R2를 적용하면 ABAB, 다시 R2를 적용하면 AAAA, R1을 적용하면 AAAB, R2를 적용하면 ABBA, R1을 적용하면 ABBB, 마지막으로 R2를 적용하면 AABB로 돌아온다. 그래서 $N = 6$의 답은 4이다.