팰린드롬 진법

사람의 손가락은 10개이므로 우리는 10진법을 사용한다. 예를 들어 $257$은 $2 \times 10^2 + 5 \times 10^1 + 7 \times 10^0$을 의미하며, 10진법의 각 자리는 $0$부터 $9$까지의 값을 가진다.

10진법 외에 자주 쓰이는 진법으로는 2진법, 8진법, 16진법이 있다. $b$진법에서 각 자리는 $0$부터 $b-1$까지의 값을 가지며, 오른쪽에서 왼쪽으로 갈수록 각 자리의 가중치는 $b^0, b^1, b^2, \dots$로 커진다.

예를 들어 10진법의 $9$는 여러 진법에서 다음과 같이 표현된다.

• 16진법: $9$
• 8진법: $11$ ($1 \times 8^1 + 1 \times 8^0 = 9$)
• 2진법: $1001$ ($1 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 9$)

이 세 표현은 모두 팰린드롬이다. 팰린드롬이란 앞에서 읽으나 뒤에서 읽으나 같은 수열을 뜻한다. 영어 단어로는 "dad", "mom", "racecar"가, 수로는 $9$, $11$, $1001$ 등이 팰린드롬이다.

10진법 정수 $X$가 주어질 때, $X$를 $b$진법으로 나타낸 값이 팰린드롬이 되는 모든 밑 $b$ ($2 \le b < X$)를 찾는 프로그램을 작성하시오.

첫째 줄에 정수 $X$가 주어진다. ($2 \le X \le 1{,}000{,}000{,}000$)

$X$를 $b$진법으로 나타냈을 때 팰린드롬이 되는 모든 $b$를 증가하는 순서대로 한 줄에 하나씩 출력한다. 그러한 $b$가 하나도 없으면 아무것도 출력하지 않는다.