Palindrome Numbers

A palindrome is a string that reads the same forwards and backwards. For example, ala and aa are palindromes, while adam is not.

Every integer can be written in base $k$ as $(a_n a_{n-1} \dots a_1 a_0)_k$, where each digit $a_i$ is an integer with $0 \le a_i < k$.

The value of $(a_n a_{n-1} \dots a_1 a_0)_k$ is $a_n \cdot k^n + a_{n-1} \cdot k^{n-1} + \cdots + a_1 \cdot k + a_0$. For example, the base-10 number $123_{10}$ has value $1 \cdot 100 + 2 \cdot 10 + 3$, and the base-8 number $123_8$ has value $1 \cdot 64 + 2 \cdot 8 + 3$.

Given an integer $n$ in base 10, write a program that finds every base among $2, 3, \dots, 10$ in which $n$ is a palindrome.

The first line contains the integer $n$. ($1 \le n \le 10^{1000}$)

If $n$ is not a palindrome in any of the bases $2, 3, \dots, 10$, print NIE. Otherwise, for each base $b$ in which $n$ is a palindrome, print the base $b$ and the representation $m$ of $n$ in base $b$ on their own line, in the format b m. Print the bases in increasing order of $b$.

For example, $n = 15$ is $1111$ in base 2 and $33$ in base 4, so it is a palindrome in both. ($1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2 + 1 = 3 \cdot 4 + 3 = 15$)