A number n may look like a palindrome in some positional bases but not others. For each base b with 2 <= b <= n-1, write n in base b as a sequence of digit values and check whether that sequence reads the same forwards and backwards. Count how many such bases make n a palindrome.
Input format
A single line with one integer n.
Output format
A single integer: the number of bases b in 2..n-1 in which n is a palindrome.
Constraints
- 3 <= n <= 100000