For this problem we are much indebted to Clive Fraser - thanks a lot!
Numbers which are palindromes read the same forwards and backwards. So 35453, 2992 and 6 are palindromes
but 1121 is not. The number 178 is not a palindrome when written in base 10. However, when written in base
8 it becomes the palindrome 262. The number 5 is a single digit palindrome in base 10 but is the
three-digit palindrome 101 in base 2. It can also be written as the two-digit palindrome 11 in base 4.
Many integers can be written as palindromes in several different bases but all integers can be written as
palindromes in some base. The trivial example of this is to write the integer N as the single-digit
palindrome N. This can be done in any base which is larger than N. The palindromes are more interesting
when they consist of more than one digit. The number 60 (base 10) is very interesting because it can be
written as a multi-digit palindrome in no fewer than 6 different bases. (You may like to find them all) The
smallest base in which 60 can be written as a multi-digit palindrome is base 9; when 60 is written as 66.
In this problem you will be given an integer N and are asked to find the smallest number base (greater than
or equal to 2) in which the integer N can be written as a palindrome.
Input and Answer
The first line of the problem will be a single integer T denoting the number of test cases.
Each of the following T lines will hold a single integer N. For each N you must find the smallest number
base (greater than 1) in which N is written as a palindrome. Give these answers, separated by spaces, as a
single string.
Example:
input:
4
5
60
207
3701
answer:
2 9 7 17