Palindrome Numbers

Interview

Time limit1sMemory limit512 MB

Summary

Given up to 50 positive integers of at most 80 digits, output for each the smallest decimal palindrome that is greater than or equal to it.

Level: Medium6 of 10
Topics: String, Greedy, Math, Implementation
Solved: No attempts yet

Problem

A word is a palindrome if it reads the same from left to right as from right to left. In this problem, a positive integer is a palindrome if its base 10 (decimal) representation reads the same from left to right as from right to left. For each number, find the smallest palindrome by value that is greater than or equal to that number. Unlike with Nascar car numbers, leading zeroes are insignificant and do not appear in any number in the input or output of this problem.

Input

The first line of input contains the number of test cases, T (1 ≤ T ≤ 50). Each of the following T lines contains a positive integer N that is no more than 80 digits in length.

Output

For each test case, output a single line containing the smallest palindrome that is greater than or equal to the input number.

Examples1

Example 1
Input
```
2
42
321
```
Expected output
```
44
323
```