Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

The following languages are only available languages for the problems from the contest

Friday the 13th, Programmers Day:

- Ada GNAT 4

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tags yet

No tag edit access

B. Triskaidekaphobia

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputTriskaidekaphobia is a fear of number 13. Ordinary people who suffer from this phobia feel uncomfortable around numbers 13, 130, 513 etc, but you, being a programmer, take this fear one step further. For example, consider number 7. It's ok when written in decimal, but written in base 4 it becomes 13, the dreadful number!

The more you think about it, the worse it looks. Number 100 has as many as 13 notations which contain 13! And there are numbers which have 13 in infinite number of their notations! Luckily, you can do any math in binary, which is completely safe from the nasty number. But still, you want to be able to estimate the level of nastiness of any number.

Your task is: given an integer *n*, find the number of different integer bases *b* (*b* ≥ 2) for which *n*, written in base *b*, contains at least one 13. Assume that "digits" of the number in bases larger than 10 are written not as letters but as decimal numbers; thus, 30 in base 16 is not 1E but (1)(14) or simply 114. Please note, that 13 must be present as a substring of notation, not a subsequence (123 doesn't contain 13).

Input

The only line of the input contains a single integer *n* (1 ≤ *n* ≤ 10^{5}).

Output

Output a single integer — the number of different integer bases *b* (*b* ≥ 2) for which *n*, written in base *b*, contains at least one 13. If there are infinitely many such bases, output -1.

Examples

Input

7

Output

1

Input

100

Output

13

Input

13

Output

-1

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/26/2017 14:11:57 (c2).

Desktop version, switch to mobile version.
User lists

Name |
---|