2013 Canadian Computing Competition, Stage 2

Day 1, Problem 1: All your base are belong to palindromes

Most of the time, humans have 10 fingers. This fact is the main reason that our numbering system is base-10: the number 257 really means 2 × 10² + 5 × 10¹ + 7 × 10⁰. Notice that each digit in base-10 is in the range from 0...9.

Of course, there are other bases we can use: binary (base-2), octal (base-8) and hexadecimal (base-16) are common bases that really cool people use when trying to impress others. In base-b, the digits are in the range from 0...b-1, with each digit (when read from right to left) being the multiplier of next larger power of b.

So, for example 9 (in base-10) is:

• 9 in base-16
• 11 in base-8 (1 × 8¹ + 1 × 8⁰ = 9)
• 1001 in base-2 (1 × 2³ + 0 × 2² + 0 × 2¹ + 1 × 2⁰ = 9)

Noticing the above, you can see that 9 is a palindrome in these 3 different bases. A palindrome is a sequence which is the same even if it is written in reverse order: English words such as dad, mom and racecar are palindromes, and numbers like 9, 11, 1001 are also palindromes.

Given a particular number X (in base-10), what bases b (2 ≤ b < X) cause the representation of X in base-b to be a palindrome?.

Input

There will be one line, containing the integer X (2 ≤ X ≤ 10⁹).

For test cases worth 80% of the points, you may assume X ≤ 10000.

Output

The output should consist of a sequence of increasing integers, each on its own line, indicating which bases have the property that X written in that base is a palindrome. Note that we will only concern ourselves with bases which are less than X, and that the first possible valid base is 2.

Sample Input

9

Sample Output

2
8

Explanation

The number 9 was shown to be a palindrome in base-2 and base-8 in the problem description. The other bases do not lead to palindromes: for example, in base-3, 9 is expressed as 100, and in base-5, 9 is expressed as 14.

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: May 19, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

The output specification should say that we only concern ourselves with bases which are *less than* X.