#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>

using namespace std;

typedef unsigned long long BigDataType;


bool isPalindrome(const string& value){
	int begin = 0;
	int end = value.size() - 1;

	while(begin < end){
		if( value[begin++] != value[end--] ) return false;
	}
	return true;
}
template<typename Type>
string convertToString(const Type& num){
	stringstream ss;
	(ss << num);
	return ss.str();
}

string getBase(BigDataType num, const unsigned int& toBase, const char * baseValue)
{	
	string baseNum = "";	
	while(num > 0){
		baseNum += baseValue[num % toBase];		
		num /= toBase;
	}
	std::reverse(baseNum.begin(), baseNum.end());
	return baseNum;
}


int main()
{		
	
	int numOfTestCases = 0;

	cin >> numOfTestCases;

	unsigned short *Answer = new unsigned short[numOfTestCases];
	unsigned short ansIndx = 0;

	const unsigned int MAX_BASE = 256;

	char baseValue[MAX_BASE];

	for(int i = 0; i < MAX_BASE; i++){
		baseValue = char(i);
	}
	
	const BigDataType MAX = 10e10;

	while(numOfTestCases--)
	{
		BigDataType num;

		cin >> num;	
		if(num < 1 || num > MAX) 
			continue;

		for(unsigned int base = 2; base < MAX_BASE; ++base)
		{
			if(isPalindrome( getBase( num, base, baseValue ) ) ){
				Answer[ansIndx++] = base;
				break;
			}					
		}
	}
 
	for(int i = 0;i < ansIndx; i++){
		cout << Answer << endl;
	}

	delete [] Answer;

	return 0; 
}

typedef unsigned long Uint32;bool IsPalindromeInBase(BigDataType num, Uint32 base){    std::vector<Uint32> thestring;    	while(num > 0)	{		thestring.push_back(num % toBase);				num /= toBase;	}		for( Uint32 i =0; i < (thestring.size() - i); ++i)	{            if ( thestring.at(i) != thestring.at(thestring.size() - i) )            {                return false;            }	}		return true;}