SPOJ PALIN, The Next Palindrome

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

Input

The first line contains integer t, the number of test cases. Integers K are given in the next t lines.

Output

For each K, output the smallest palindrome larger than K.

Example

Input:
2
808
2133

Output:
818
2222

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <cstring>
using namespace std;
typedef long long int lli;
typedef long unsigned long llu;
#define mem_prep(varx) memset(varx,0,sizeof(varx))
#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size())
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define repe(i,a,n)  for(int i=(a);i<=(n);i++)
#define forsz(i,a,v) rep(i,a,sz(v))
#define repsz(i,v) rep(i,0,sz(v))
#define vi vector<int>
#define vs vector<string>
void prepare( )
{
#ifdef WIN32
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
}

string s;

bool checkpalin(){
  char left='a',right='a';
  if(sz(s)%2){
    for (int i = sz(s)/2-1,j=sz(s)/2+1; i >= 0; --i,++j){
      left=s[i];right=s[j];
      if(left>right)return false; //makepalin directly
      if(left<right)return true;
    }
  }
  else{
    for (int i = sz(s)/2-1,j=sz(s)/2; i >= 0; --i,++j){
      left=s[i];right=s[j];
      if(left>right)return false; //makepalin directly
      if(left<right)return true;
    }
  }
  return true; //palin or add 1 to mid
}

void solvecarry(){
  for (int i = sz(s)/2; i >= 0; --i){
    if(s[i]=='9'){
      s[i]='0';
      if(i==0)s.insert(0, "1");
    }
    else {
      s[i]++;
      return;
    }
  }
}
void makepalin(){
  for (int i = 0,j=sz(s)-1; i < sz(s)/2; ++i,--j){
    s[j]=s[i];
  }
}
int main(){
  int nTests;
  scanf("%d ",&nTests);
  repe(test,1,nTests) {
    cin>>s;
    if(sz(s)%2){ //odd
      if(!checkpalin()){makepalin();cout<<s<<endl;continue;} //makepalin directly
      if(s[sz(s)/2]=='9')solvecarry();
      else s[sz(s)/2]++;
      makepalin();
    }
    else{ //even
      char lefty,righty;
      int left=sz(s)/2-1,right=sz(s)/2;
      if(!checkpalin()){makepalin();cout<<s<<endl;continue;} //makepalin directly
      lefty=s[left];righty=s[right];
      if(lefty==righty){
if(s[left]=='9')solvecarry();
else s[left]=s[right]=s[left]+1;
makepalin();
      }
      if(lefty<righty){
s[left]++;
s[right]=s[left];
makepalin();
      }
    }
    cout<<s<<endl;
  }
  return 0;
}