Note: If no solution exists, output -1.

譲れない夢なら私にも きっとある 信じてる 
不容退让的梦想我也有 坚信你和我今后的可能

高鳴るこの胸の奥深く 灯ったの 静かに情熱が 今 
那潜藏心底的炙热情感 涌上心头轰鸣喷出之时 就在此刻

  99届，愛城華恋，「世界を灰にするまで」《少女歌剧 Revue Starlight》

Given a number $x$, find the smallest $y$ such that $y + y\texttt{.reverse()} = x$, or indicate that no solution exists. Here, reverse() refers to the number obtained by reversing the string representation of $y$. $y$ cannot have leading zeros, but $y\texttt{.reverse()}$ may.

Input

The first line contains a positive integer $T$, representing the number of test cases.

Each of the following lines contains a non-negative integer $x$, representing the number to query.

Output

Output $T$ lines, each containing a non-negative integer $y$ representing the corresponding answer.

Examples

Input 1

5
3982
198
121
1017610
1998

Output 1

1991
99
29
107909
999

Constraints

Let $L$ be the length of the input string $x$.

For $20\%$ of the data, $L \le 5$.

For $40\%$ of the data, $L \le 50$.

For $60\%$ of the data, $L \le 1,000$.

For $100\%$ of the data, $1 \le T \le 5$, $1 \le L \le 10^6$.

Note

The provided sample cases cover all answers for $0 \le x \le 9,999$.