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