#include<iostream>#include<cmath>#include<string>#include<map>using namespace std;#define EPS 1e-6namespace{string& remove_leading_zero(string &s){while (s[0] == '0')s.erase(0, 1);return s;}pair<string, int> divide(const string &s, int n){if (s == "0")return make_pair("0", 0);string t = "0";int rem = 0;for (size_t i = 0; i < s.size(); i++){rem = rem * 10 + (s[i] - '0');t += (rem / n + '0');rem = rem % n;}return make_pair(remove_leading_zero(t), rem);}}int main(){map<size_t, int> M;for (int i = 3; i <= 100000; i++){double d = i * log10(i);size_t t = (size_t) (d + 1 + EPS);M[t] = i;}int T;string s;cin >> T >> ws;while (T--){cin >> s;if (s.size() == 1){if (s == "1")cout << 1 << endl;else if (s == "4")cout << 2 << endl;elsecout << -1 << endl;}else{int N = M[s.size()];pair<string, int> p = divide(s, N);bool can = true;int count = 0;while (p.first != "1"){if (count++ == 3)break;if (p.second != 0){can = false;break;}p = divide(p.first, N);}cout << (can ? N : -1) << endl;}}return 0;}
