Find the next palindrome

gistfile1.cpp

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string k;
        cin >> k;

        int z = k.length() - 1;

        while(z >= 0 && k[z] == '9'){
            k[z]='0';
            z--;
        }
        if(z >= 0)
            k[z]=k[z] + 1;
        else{
            k = k.insert(0,"1");
        }

        int l = k.length();
        int s = (l >> 1) - 1;
        bool flag = 0;
        bool e = l % 2 == 0;

        for(int i = s; i >= 0; i--)
        {
            int d = i + ((s - i) << 1) + 1;

            if(!e)
                d++;

            char item1 = k[i];
            char item2 = k[d];


            if(item1 < item2 && !flag)
            {
                if(!e)
                {
                    int mid = l >> 1;
                    if(k[mid] == '9')
                    {
                        k[mid] = '0';
                        int j = mid - 1;
                        int nx = j + ((s - j) << 1) + 2;

                        while(j >= 0 && k[j] == '9')
                        {
                            k[j]='0';
                            j--;
                            k[nx]='0';
                            nx++;
                        }

                        if(j < 0)
                        {
                            k = k.insert(0,"0");
                            k = k.insert(k.length() - 1,"0");
                            j = 0;
                        }

                        k[j] = k[j] + 1;
                        int cv = j + ((s - j) << 1) + 2;
                        k[cv] =k[j];

                    }
                    else
                        k[mid]=k[mid] + 1;
                }
                else
                {
                    if(!flag)
                    {
                        int x = s;
                        int ind = x + ((s - x) << 1) + 1;

                        while(x >= 0 && k[x] == '9'){
                            k[x] = '0';
                            k[ind] = k[x];
                            ind++;
                            x--;
                        }

                        if(x < 0){
                            k = k.insert(0,"0");
                            k = k.insert(k.length() - 1,"0");
                            x = 0;
                        }

                        k[x] = k[x] + 1;
                        int cv =  x + ((s - x) << 1) + 1;
                        k[cv] = k[x];
                    }
                    else
                        k[d] = k[i];
                }
                flag = 1;
            }
            else
            {
                if(item1 > item2){
                    k[d] = k[i];
                    flag=1;
                }
            }

            if(flag){
                k[d] = k[i];
            }
        }
        cout << k << endl;
    }
    return 0;
}