팰린드롬 숫자

팰린드롬은 앞에서 읽으나 뒤에서 읽으나 똑같은 문자열이다. 예를 들어 ala와 aa는 팰린드롬이지만, adam은 팰린드롬이 아니다.

모든 정수는 $k$진법으로 $(a_n a_{n-1} \dots a_1 a_0)_k$ 처럼 나타낼 수 있다. 이때 각 자리 $a_i$는 $0$ 이상 $k$ 미만의 정수이다.

$(a_n a_{n-1} \dots a_1 a_0)_k$가 나타내는 값은 $a_n \cdot k^n + a_{n-1} \cdot k^{n-1} + \cdots + a_1 \cdot k + a_0$ 이다. 예를 들어 10진법 수 $123_{10}$의 값은 $1 \cdot 100 + 2 \cdot 10 + 3$이고, 8진법 수 $123_8$의 값은 $1 \cdot 64 + 2 \cdot 8 + 3$이다.

10진법으로 주어진 정수 $n$을 $2, 3, \dots, 10$진법으로 나타냈을 때, 팰린드롬이 되는 모든 진법을 찾는 프로그램을 작성하시오.

첫째 줄에 정수 $n$이 주어진다. ($1 \le n \le 10^{1000}$)

$n$을 $2, 3, \dots, 10$진법으로 나타냈을 때 팰린드롬이 되는 경우가 하나도 없으면 NIE를 출력한다. 그렇지 않으면 팰린드롬이 되는 각 진법 $b$에 대해 진법 $b$와 $n$을 $b$진법으로 나타낸 수 $m$을 b m 형식으로 한 줄에 하나씩 출력한다. 출력은 $b$가 증가하는 순서로 한다.

예를 들어 $n = 15$는 2진법에서 $1111$, 4진법에서 $33$이 되어 두 경우 모두 팰린드롬이다. ($1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2 + 1 = 3 \cdot 4 + 3 = 15$)