Preparando MOJI

Triskaidekaphobia

2000ms 262144K

Description:

Triskaidekaphobia 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 ≤ 105).

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.

Sample Input:

7

Sample Output:

1

Sample Input:

100

Sample Output:

13

Sample Input:

13

Sample Output:

-1

Informação

Codeforces

Provedor Codeforces

Código CF345B

Tags

*special

Submetido 0

BOUA! 0

Taxa de BOUA's 0%

Datas 09/05/2023 08:46:36

Relacionados

Nada ainda