\(f_{x,a}\) := \(x\) を \(a\) 個並べた数
とする． \(N\) が \(k\) 桁， \(y\) を \(N\) の先頭 \(p\) 桁， \(p \geq 1\) とする．
基本的に答えは $$ max_{k \equiv 0 \ mod \ p} (f_{y, k/p}, f_{y-1, k/p}) \ \cdots \ (0). $$ しかし，これだと \(N = 10^{i}\) の形のときに間違い． この場合は $$ 10^{i} - 1 \ \cdots \ (1) $$ が正しい答え．
まとめると， 答えの候補を \(m\) として，
- \(m\) が \(k\) 桁の場合は (0),
- \(m\) が \(k-1\) 桁の場合は (1),
- \(m\) が \(k-2\) 桁以下の場合は，(1)より小さいので答えにならない．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
ll f(ll x){
ll k = 0;
while(x){
x /= 10;
k ++;
}
return k;
}
string ll_to_s(long long x, long long bas = 10){
string s;
while(x){
s.push_back(x % bas + '0');
x /= bas;
}
reverse(all(s));
return s;
}
long long s_to_ll(string s, long long bas = 10){
long long x = 0;
for(int i = 0; i < s.size(); i++){
x = bas*x + (s[i] - '0');
}
return x;
}
int main() {
ll t; cin >> t;
rep(ti,t){
ll n; cin >> n;
ll ans = -1;
// k = f(n) = nの桁数
// k-1 桁の periodic 数 s.t. n 以下
ll x = 0;
rep(i,f(n)-1){
x = 10*x + 9;
}
chmax(ans, x);
// k 桁の periodic 数 s.t. n 以下
srep(p,1,20) if(f(n)%p==0 && f(n)/p >= 2){
string s;
string vn = ll_to_s(n);
rep(i,p){
s.push_back(vn[i]);
}
rep(k,2){
if(k == 1){
ll ys = s_to_ll(s);
ys--;
s = ll_to_s(ys);
}
string t;
rep(i, f(n)/p){
t.insert(t.end(), all(s));
}
// if(vn >= t){
if(n >= s_to_ll(t)){
chmax(ans, s_to_ll(t));
break;
}
}
}
cout << ans << endl;
}
return 0;
}
