next smaller palindrome

#include <bits/stdc++.h>
using namespace std;
vector<int> nextPalin(vector<int>&num){
    int n=num.size();
    int mid=n/2;
    int i=mid-1;
    int j;
    n%2 ? j=mid+1 : j=mid;
    // cout<<i<<" "<<j<<endl;
    while(i>=0&&j<n&&num[i]==num[j]){
        i--;
        j++;
    }
    bool leftSmaller=false;
    if(i<0||num[i]<num[j])
        leftSmaller=true;
    while(i>=0&&j<n){
        num[j]=num[i];
        i--;
        j++;
    }
        // cout<<i<<" "<<j<<endl;

    if(leftSmaller){
        int carry=1;
        i=mid-1;
        if(n%2){
            num[mid]+=(carry);
            carry=num[mid]/10;
            num[mid]=num[mid]%10;
            j=mid+1;

        }
        else
            j=mid;
        while(i>=0){
            num[i]+=carry;
            carry=num[i]/10;
            num[i]=num[i]%10;
            num[j]=num[i];
            i--;
            j++;
        }
    }
    return num;

}
bool all9s(vector<int>&num){
    int n=num.size();
    for(int i=0;i<n;i++)
        if(num[i]!=9)
            return false;
    return true;
}
vector<int> allAre9s(vector<int>&num){
    int n=num.size();
    vector<int>ans(n+2);
    ans[0]=1;
    ans[n+1]=1;
    for(int i=0;i<n;i++)
        ans[i+1]=0;
    return ans;
}
int main() {
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        int n=s.size();
        vector<int>num(n);
        for(int i=0;i<n;i++){
            num[i]=s[i]-'0';
        }

        vector<int>ans;
        if(all9s(num))
            ans=allAre9s(num);
        else
            ans=nextPalin(num);
        string a="";
        for(int i=0;i<ans.size();i++){
            a+=(ans[i]+'0');
        }
        cout<<a<<endl;

    }
    return 0;
}