← 返回题目列表

Codeforces · 345/B

B. 特里斯凯德恐惧症

中文机器翻译题面 查看原题

Triskaidekaphobia 是对数字 13 的恐惧。患有这种恐惧症的普通人对数字 13、130、513 等感到不舒服,但作为一名程序员,你可以将这种恐惧更进一步。例如,考虑数字 7。用十进制书写时没问题,但用 4 进制书写时,它就变成了 13,一个可怕的数字!

你越想,它看起来就越糟糕。数字100有多达13个符号,其中包含13!还有一些数字的记数法有无数种,都是 13!幸运的是,您可以用二进制进行任何数学运算,这完全不受讨厌的数字的影响。但是,您仍然希望能够估计任何数字的肮脏程度。

你的任务是:给定一个整数n,找到不同整数基数b(b≥2)的个数,其中以b为基数的n至少包含一个13。假设大于10的基数中的数字的“数字”不是写成字母而是写成十进制数;因此,以 16 为基数的 30 不是 1E,而是 (1)(14) 或只是 114。请注意,13 必须作为表示法的子字符串而不是子序列出现(123 不包含 13)。

输入

输入的唯一行包含单个整数 n (1 ≤ n ≤ 105)。

输出

输出一个整数 — 不同整数基数 b (b ≥ 2) 的数量,其中以 b 为基数的 n 至少包含一个 13。如果有无限多个这样的基数,则输出 -1。

示例

输入 #1

7

输出 #1

1

输入 #2

100

输出 #2

13

输入 #3

13

输出 #3

-1