Canadian Computing Competition: 2013 Stage 2, Day 1, Problem 1

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 \times 10^2 + 5 \times 10^1 + 7 \times 10^0~. Notice that each digit in base-~10~ is in the range from ~0 \dots 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 \dots b-1~, with each digit (when read from right to left) being the multiplier of the next larger power of ~b~.

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

• ~9~ in base-~16~
• ~11~ in base-~8~ (~1 \times 8^1 + 1 \times 8^0 = 9~)
• ~1001~ in base-~2~ (~1 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 9~)

Noticing the above, you can see that ~9~ is a palindrome in these three 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~, and ~1001~ are also palindromes.

Given a particular number ~X~ (in base-~10~), for what bases ~b~ (~2 \le b \le X~) is the representation of ~X~ in base-~b~ a palindrome?

Input Specification

There will be one line, containing the integer ~X~ (~2 \le X \le 10^9~).

For test cases worth ~80\%~ of the points, you may assume ~X \le 10^4~.

Output Specification

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

Output for Sample Input

2
8

Explanation of Output for Sample Input

The number ~9~ was shown to be a palindrome in base-~2~ and in 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~.