The Next Palindrome

 The Next Palindrome

PROBLEM STATEMENT :

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

Warning: large Input/Output data, be careful with certain languages

SOLUTION : 

 
#include <iostream>
#include<string>
using namespace std;

int main() {
	long long int i,l;
	int t;
	cin>>t;
	while(t--)
	{
	    string k,x;
	    cin>>k;
	    x=k;
	    l=k.size();
	    for(i=l/2;i<l;++i) x[i]=x[l-i-1];
	    if(x>k) 
	    {
	        cout<<x<<"\n";
	        continue;
	    }
	    for(i=(l-1)/2;i>=0;--i) 
	    {
	        if(x[i]!='9') 
	        {
	            x[i]++;
	            break;
	        }
	        else x[i]='0';
	    }
	    for(i=l/2;i<l;++i) x[i]=x[l-i-1];
	    if(x[0]=='0')
	    {
	        x+='1';
	        x[0]='1';
	    }
	    cout<<x<<"\n";
	}
	return 0;
}

Never Stop Learning !!