Solved this problem with the help of BigInt as well, but gave TLE.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static char[] getNextNum(char[] a) {
boolean carry = true;
for (int i = a.length - 1; i >= 0; i--) {
if (!carry) break;
if (a[i] == '9') {
carry = true;
a[i] = '0';
} else {
a[i] = (char) (a[i] + 1);
carry = false;
}
}
char[] b;
if (carry) {
b = new char[a.length + 1];
b[0] = '1';
for (int i = 0; i < a.length; i++) {
b[i + 1] = a[i];
}
} else {
b = a;
}
return b;
}
public static int compare(char[] a, char[] b) {
if (a.length < b.length) return -1;
if (a.length > b.length) return 1;
for (int i = a.length - 1; i >= 0; i--) {
if (a[i] > b[i]) return 1;
if (a[i] < b[i]) return -1;
}
return 0;
}
public static boolean isPalindrome(char[] a) {
for (int i = 0; i < a.length / 2; i++) {
if (a[i] != a[a.length - i - 1]) return false;
}
return true;
}
public static char[] reverse(char[] a) {
char[] b = new char[a.length];
for (int i = 0; i < a.length; i++) {
b[i] = a[a.length - i - 1];
}
return b;
}
public static char[] subArray(char[] a, int x, int y) {
char[] b = new char[y - x];
for (int i = x; i < y; i++) {
b[i - x] = a[i];
}
return b;
}
public static class InputReader {
private BufferedReader reader;
private StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public long nextLong() {
return Long.parseLong(next());
}
public int nextInt() {
return Integer.parseInt(next());
}
}
public static void main(String[] args) {
InputReader in = new InputReader(System.in);
int T = in.nextInt();
while (T-- != 0) {
String num = in.next();
if (num.length() == 1) {
System.out.println(11);
continue;
}
char[] a = num.toCharArray();
a = getNextNum(a);
if (isPalindrome(a)) {
System.out.println(a);
continue;
}
if (a.length % 2 == 0) {
char[] pre = subArray(a, 0, a.length / 2);
char[] post = subArray(a, a.length / 2, a.length);
if (compare(post, reverse(pre)) > 0) {
pre = getNextNum(pre);
}
System.out.print(pre);
System.out.println(reverse(pre));
} else {
char[] pre = subArray(a, 0, a.length / 2 + 1);
char[] post = subArray(a, a.length / 2 + 1, a.length);
char[] evenPart = subArray(pre, 0, pre.length - 1);
if (compare(post, reverse(evenPart)) > 0) {
pre = getNextNum(pre);
}
System.out.print(pre);
System.out.println(reverse(subArray(pre, 0, pre.length - 1)));
}
}
}
}