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
joist: 2016-06-27 01:49:37

majorly, just 2 different cases (condition) + 1 exception of all 9s.

codeonwort: 2016-06-26 20:26:14

Solved it but my case condition is really clumsy - six conditions! I wonder if there exists a more elegant way.

mickey_v: 2016-06-26 20:17:41

999
9999
the most tricky one

Last edit: 2016-06-26 20:18:37
joist: 2016-06-26 16:03:13

0.06s & 4.2 MB is not so bad?

ag_2207: 2016-06-21 20:53:22

I'm getting success on Ideone but Wrong answer on spoj
someone plzz help me

baadshah_: 2016-06-21 13:34:11

AC in one go!!! but took time to implement and check for edge cases

r_jayanth2: 2016-06-20 10:11:34

Why my solution which increments the number by 1 and check if its palindrome(converting to strings and compare) is giving WA?

ashwin_07: 2016-06-19 08:28:57

tricky cases
input : 2
8879
8890

output:
8888
8998

kpiyush26: 2016-06-18 19:02:35

what is the reason for getting runtime error(NZEC) IN JAVA?

vaibhavahuja: 2016-06-18 01:55:59

TLE. :(


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 PERL 6

Problem's scores 1 vote

Concept difficulty
Concept difficulty 40%
Implementation difficulty
Implementation difficulty 49%
134 5