앞으로 읽든 뒤로 읽든

면접 대비

시간 제한1초메모리 제한1024 MB

요약

N이 주어질 때, 2부터 N까지의 진법 중 N을 그 진법으로 나타내면 앞뒤가 같은 진법을 오름차순으로 구합니다.

난이도: 보통10점 중 5점
유형: 정수론, 수학, 구현
정답자: 아직 제출이 없습니다

문제

먼 행성계에는 태양이 하나 있고 행성이 N − 1개 있다. 각 행성은 2부터 N까지의 서로 다른 정수로 구분된다. 행성 b에서는 수를 b진법으로 표현한다.

회문은 앞에서 읽으나 뒤에서 읽으나 같은 수이다. 회문인지 판단할 때 앞쪽의 0은 세지 않는다.

같은 수라도 행성에 따라 회문일 수도 있고 아닐 수도 있다. 예를 들어 10진법에서 33은 회문이다. 33은 2진법과 32진법에서도 회문이지만, 3진법과 33진법에서는 회문이 아니다. $33_{10} = 100001_2 = 1020_3 = 11_{32} = 10_{33}$ 이기 때문이다.

입력

한 줄에 정수 N이 주어진다. ( $2 \le N \le 10^{12}$ ) N은 10진법으로 표현된다.

출력

N이 회문이 되는 행성의 식별자를 증가하는 순서로 한 줄에 출력한다. 식별자는 10진법으로 출력하며, 2 이상 N 이하이다. N이 어떤 행성에서도 회문이 아니면 *을 출력한다.

예제3

예제 1
입력
```
33
```
예상 출력
```
2 10 32
```
예제 2
입력
```
3
```
예상 출력
```
2
```
예제 3
입력
```
2
```
예상 출력
```
*
```