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


hide comments
dante: 2014-09-15 09:53:06

why its showing wrong answer? its running perfectly in borland c++, dev c++ and gcc in linux.
ID-12377818

Last edit: 2014-09-15 09:55:33
Ignacio Cortorreal: 2014-09-14 22:47:42

As Yevgen Yampolskiy said, last line does not have terminating '\n'. I'll consider that on next problems. :P

Ignacio Cortorreal: 2014-09-14 17:23:05

Why is this answer wrong?

http://www.spoj.com/files/src/12373877/

Last edit: 2014-09-14 17:24:17
akash agrawal: 2014-09-14 00:49:53

code is running successfully in ideone but
here it is given wrong answer

Vishal: 2014-09-08 16:11:17

Running in ideone with time 0.11 here it shows time limit exceeded plz help
<snip>

Last edit: 2022-07-26 22:28:38
manasniec19@gmail.com: 2014-09-01 16:58:12

constraint on no of test cases??

Last edit: 2014-09-01 16:58:39
sitaram: 2014-08-28 21:45:58

running in codeblock...........but showing wrong answer here

Nandan Mankad: 2014-08-27 16:41:55

Really Nice One! Finally AC after a good amount of struggle!

Utkarsh: 2014-08-26 15:39:54

What should be the output in case of single digit integers?

Leppy: Why should one digit be handled differently than 3 or 5 or 1000000 digits?

Last edit: 2014-08-27 18:21:09
Nazib Sorathiya: 2014-08-24 15:13:05

Time Limit Exceeded !!!!!!!
Common in my system there is no time lag for output and also on Ideone.com(online terminal for gcc)time shown is 0,then how come time limit is exceeding


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

Problem's scores 1 vote

Concept difficulty
Concept difficulty 37%
Implementation difficulty
Implementation difficulty 50%
467 16