Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

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

Friday the 13th, Programmers Day:

- Ada GNAT 4

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-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/18/2018 23:25:14 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|