//
// palin5.c
// Spoj.pl
//
// Created by Subodh Kamble on 17/04/13.
// Copyright (c) 2013 Subodh Kamble. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
int t , i;
char *input , *output ;
unsigned long long int l , x , y , mid ;
int NoPalindrome = 1 ;
while (t--)
{
input
= (char *)malloc(1000000);
NoPalindrome = 1 ;
i = 0 ;
for(i = 0 ; i< l ; i++)
{
if(input[i]!='9')
break;
}
if(i==l)
{
output[0]='1';
output[l]='1';
for(i=1;i<l;i++)
output[i]='0';
output[l+1]='\0';
break;
}
//make a string containig all digits of input
//find the mid number
output[l-1]=output[l-1]+1;
if (l%2==0)
{
//even
mid = l/2 ;
x = mid - 1 ;
y = mid ;
while (y!=l)
{
if (output[x] < output[y])
{
output[x]=output[x]+1 ;
output[y]=output[x];
break ;
}
else if (output[x] == output[y] && output[x] != '\0')
{
x--;
y++;
if(output[x] < output[y])
{
output[x+1] = output[x+1]+1;
output[y-1] = output[y-1]+1;
}
}
else if (output[x] == '9' && output[y]== '9')
{
while (output[x]== output[y])
{
x--;
y++;
}
if (output[x] < output[y]) // 1997 case
{
output[x]=output[x]+1;
output[y]=output[x];
for (i=x+1; i<=y-1; i++)
output[i]='0';
}
break;
}
else if (output[x] > output[y])
{
output[y]=output[x];
break ;
}
x--;
y++;
}
while (y <= l-1 )
{
output[y]=output[x];
x--;
y++;
}
}
else
{
//odd
mid = l/2 ;
x = mid - 1 ;
y = mid + 1;
while (y!=l)
{
if (output[x] <= output[y] && output[mid] != '9')
{
output[mid]=output[mid]+1;
break ;
}
else if (output[x] <= output[y] && output[mid] == '9')
{
while (output[x] == output[y])
{
x--;
y++;
}
if (output[x] < output[y]) // 14897 case
{
output[x]=output[x]+1;
output[y]=output[x];
for (i=x+1; i<=y-1; i++)
output[i]='0';
}
break;
}
else if (output[x] > output[y])
{
output[y]=output[x];
break ;
}
x--;
y++;
}
while (y <= l-1 )
{
output[y]=output[x];
x--;
y++;
}
}
//check
x = 0 ;
y = l -1 ;
while(output[x]==output[y] && output[x] != '\0')
{
x++;
y--;
}
if(x-1 == l-1)
{
NoPalindrome = 0 ;
}
}
return 0 ;
}
Ly8KLy8gIHBhbGluNS5jCi8vICBTcG9qLnBsCi8vCi8vICBDcmVhdGVkIGJ5IFN1Ym9kaCBLYW1ibGUgb24gMTcvMDQvMTMuCi8vICBDb3B5cmlnaHQgKGMpIDIwMTMgU3Vib2RoIEthbWJsZS4gQWxsIHJpZ2h0cyByZXNlcnZlZC4KLy8KCiNpbmNsdWRlIDxzdGRpby5oPgojaW5jbHVkZSA8c3RkbGliLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KCmludCBtYWluKCkKewogICAgaW50ICB0ICwgaTsKICAgIGNoYXIgKmlucHV0ICwgKm91dHB1dCA7CiAgICB1bnNpZ25lZCBsb25nIGxvbmcgaW50IGwgLCB4ICwgeSAsIG1pZCAgOwogICAgaW50IE5vUGFsaW5kcm9tZSA9IDEgOwogICAgc2NhbmYoIiVkIiwmdCk7CgogICAgd2hpbGUgKHQtLSkKICAgIHsKICAgICAgICBpbnB1dCA9IChjaGFyICopbWFsbG9jKDEwMDAwMDApOwogICAgICAgIHNjYW5mKCIlcyIsaW5wdXQpOwogICAgICAgIGwgPSBzdHJsZW4oaW5wdXQpOwoKICAgICAgICBOb1BhbGluZHJvbWUgPSAxIDsKICAgICAgICBpID0gMCA7CiAgICAgICAgZm9yKGkgPSAwIDsgaTwgbCA7IGkrKykKICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaWYoaW5wdXRbaV0hPSc5JykKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgfQoKICAgICAgICBpZihpPT1sKQogICAgICAgIHsKICAgICAgICAgICAgb3V0cHV0ID0gbWFsbG9jKGwrMik7CiAgICAgICAgICAgIG91dHB1dFswXT0nMSc7CiAgICAgICAgICAgIG91dHB1dFtsXT0nMSc7CiAgICAgICAgICAgIGZvcihpPTE7aTxsO2krKykKICAgICAgICAgICAgICAgIG91dHB1dFtpXT0nMCc7CiAgICAgICAgICAgIG91dHB1dFtsKzFdPSdcMCc7CiAgICAgICAgICAgIHByaW50ZigiJXNcbiIsb3V0cHV0KTsKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgfQoKCiAgICAgICAgLy9tYWtlIGEgc3RyaW5nIGNvbnRhaW5pZyBhbGwgZGlnaXRzIG9mIGlucHV0CiAgICAgICAgb3V0cHV0ID0gbWFsbG9jKGwpOwogICAgICAgIHN0cmNweShvdXRwdXQsaW5wdXQpOwoKICAgICAgICAgICAvL2ZpbmQgdGhlIG1pZCBudW1iZXIKICAgICAgICAgICAgbCA9IHN0cmxlbihvdXRwdXQpOwogICAgICAgICAgICBvdXRwdXRbbC0xXT1vdXRwdXRbbC0xXSsxOwogICAgICAgICAgICBpZiAobCUyPT0wKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAvL2V2ZW4KICAgICAgICAgICAgICAgIG1pZCA9IGwvMiA7CiAgICAgICAgICAgICAgICB4ID0gbWlkIC0gMSA7CiAgICAgICAgICAgICAgICB5ID0gbWlkIDsKCiAgICAgICAgICAgICAgICB3aGlsZSAoeSE9bCkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBpZiAob3V0cHV0W3hdIDwgb3V0cHV0W3ldKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgb3V0cHV0W3hdPW91dHB1dFt4XSsxIDsKICAgICAgICAgICAgICAgICAgICAgICAgb3V0cHV0W3ldPW91dHB1dFt4XTsKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWsgOwoKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgZWxzZSBpZiAob3V0cHV0W3hdID09IG91dHB1dFt5XSAmJiBvdXRwdXRbeF0gIT0gJ1wwJykKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIHgtLTsKICAgICAgICAgICAgICAgICAgICAgICAgeSsrOwogICAgICAgICAgICAgICAgICAgICAgICBpZihvdXRwdXRbeF0gPCBvdXRwdXRbeV0pCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBvdXRwdXRbeCsxXSA9IG91dHB1dFt4KzFdKzE7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgb3V0cHV0W3ktMV0gPSBvdXRwdXRbeS0xXSsxOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGVsc2UgaWYgKG91dHB1dFt4XSA9PSAnOScgJiYgb3V0cHV0W3ldPT0gJzknKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgd2hpbGUgKG91dHB1dFt4XT09IG91dHB1dFt5XSkKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgeC0tOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgeSsrOwoKICAgICAgICAgICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgICAgICAgICAgaWYgKG91dHB1dFt4XSA8IG91dHB1dFt5XSkgICAgICAgICAgICAgICAgICAgICAgICAgLy8gMTk5NyBjYXNlCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBvdXRwdXRbeF09b3V0cHV0W3hdKzE7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgb3V0cHV0W3ldPW91dHB1dFt4XTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBmb3IgKGk9eCsxOyBpPD15LTE7IGkrKykKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgb3V0cHV0W2ldPScwJzsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGVsc2UgaWYgKG91dHB1dFt4XSA+IG91dHB1dFt5XSkKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIG91dHB1dFt5XT1vdXRwdXRbeF07CiAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrIDsKICAgICAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgICAgIHgtLTsKICAgICAgICAgICAgICAgICAgICB5Kys7CiAgICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIHdoaWxlICh5IDw9IGwtMSApCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgb3V0cHV0W3ldPW91dHB1dFt4XTsKICAgICAgICAgICAgICAgICAgICB4LS07CiAgICAgICAgICAgICAgICAgICAgeSsrOwogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIC8vb2RkCiAgICAgICAgICAgICAgICBtaWQgPSBsLzIgOwogICAgICAgICAgICAgICAgeCA9IG1pZCAtIDEgOwogICAgICAgICAgICAgICAgeSA9IG1pZCArIDE7CgogICAgICAgICAgICAgICAgd2hpbGUgKHkhPWwpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaWYgKG91dHB1dFt4XSA8PSBvdXRwdXRbeV0gJiYgb3V0cHV0W21pZF0gIT0gJzknKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgb3V0cHV0W21pZF09b3V0cHV0W21pZF0rMTsKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWsgOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBlbHNlIGlmIChvdXRwdXRbeF0gPD0gb3V0cHV0W3ldICYmIG91dHB1dFttaWRdID09ICc5JykKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIHdoaWxlIChvdXRwdXRbeF0gPT0gb3V0cHV0W3ldKQogICAgICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB4LS07CiAgICAgICAgICAgICAgICAgICAgICAgICAgICB5Kys7CgogICAgICAgICAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgICAgICAgICBpZiAob3V0cHV0W3hdIDwgb3V0cHV0W3ldKSAgICAgICAgICAgICAgICAgICAgICAgICAvLyAxNDg5NyBjYXNlCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG91dHB1dFt4XT1vdXRwdXRbeF0rMTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG91dHB1dFt5XT1vdXRwdXRbeF07CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBmb3IgKGk9eCsxOyBpPD15LTE7IGkrKykKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBvdXRwdXRbaV09JzAnOwogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBlbHNlIGlmIChvdXRwdXRbeF0gPiBvdXRwdXRbeV0pCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBvdXRwdXRbeV09b3V0cHV0W3hdOwogICAgICAgICAgICAgICAgICAgICAgICBicmVhayA7CiAgICAgICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgICAgICB4LS07CiAgICAgICAgICAgICAgICAgICAgeSsrOwogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgICB3aGlsZSAoeSA8PSBsLTEgKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIG91dHB1dFt5XT1vdXRwdXRbeF07CiAgICAgICAgICAgICAgICAgICAgeC0tOwogICAgICAgICAgICAgICAgICAgIHkrKzsKICAgICAgICAgICAgICAgIH0KCgoKICAgICAgICAgICAgfQoKCgogICAgICAgICAgICAvL2NoZWNrCiAgICAgICAgICAgIHggPSAwIDsKICAgICAgICAgICAgeSA9IGwgLTEgOwogICAgICAgICAgICB3aGlsZShvdXRwdXRbeF09PW91dHB1dFt5XSAmJiBvdXRwdXRbeF0gIT0gJ1wwJykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgeCsrOwogICAgICAgICAgICAgICAgeS0tOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmKHgtMSA9PSBsLTEpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIE5vUGFsaW5kcm9tZSA9IDAgOwogICAgICAgICAgICAgICAgcHJpbnRmKCIlc1xuIixvdXRwdXQpOwogICAgICAgICAgICB9CgoKCgogICAgICAgIH0KCiAgICBmcmVlKGlucHV0KTsKICAgIGZyZWUob3V0cHV0KTsKCiAgICByZXR1cm4gMCA7Cn0K