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

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


Added by:adrian
Date:2004-05-01
Time limit:2s-9s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6

hide comments
2016-03-14 18:52:26
aviben its 1111 for 1010
2016-03-12 22:12:56
getting runtime error NZEC ..please help
2016-03-12 18:37:58
Firstly i write code in Java but got TLE and then i tried in C++ and got accepted in 0.08 sec .

Last edit: 2016-03-12 18:38:28
2016-03-11 17:37:01
Check for inputs 1010, and similar pattern ones ppl who are getting wrong answer
2016-03-10 05:03:01
why we get time limit exceeded in java ?
2016-03-08 13:13:03
i am new here, im getting time limit exceeded in java for this. but i have not used loop at all (xcept for no. of testcases) anyone can help me ?

Last edit: 2016-03-10 04:59:38
2016-03-05 18:05:17 ISHPREET
A must do question.. Got ac after many WA... felt Great...
2016-02-22 16:27:27
Ive spent all my free time of the last week on this problem! (so like 4 hours tops >:[ ) I was making it way more complicated than it needed to be but as someone else said: it was humbling. Lots of little finicky potential problems. My suggestion is if you still arent getting it run it with ALOT of random numbers in a large range (i did rand() % 100000 for like 10000 iterations) and have it show the cases where you get them wrong and take it from there
2016-02-21 20:27:32
is it possible in spoj to know for which input values the code is going wrong?? reply asap .
2016-02-21 07:07:31
I am getting wrong output but it is working correctly.My solution id is 16329198.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.