Recently, Nvoenewr learnt palindromes in his class.

A palindrome is a nonnegative integer that is the same when read from left to right and when read from right to left. For example, 0, 1, 2, 11, 99, 232, 666, 998244353353442899 are palindromes, while 10, 23, 233, 1314 are not palindromes.

Now, given a number, Nvoenewr can determine whether it’s a palindrome or not by using loops which his teacher has told him on the class. But he is now interested in another question: What’s the K-th palindrome? It seems that this question is too difficult for him, so now he asks you for help.

Nvoenewr counts the number from small to big, like this: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101 and so on. So the first palindrome is 0 and the eleventh palindrome is 11 itself.
Nvoenewr may ask you several questions, and the K may be very big.

Input
The first line contains one integer T(T <= 20) —— the number of questions that Nvoenewr will ask you.

Each of the next T lines contains one integer K. You should find the K-th palindrome for Nvoenewr.

Let’s say K is a n-digit number. It’s guaranteed that K >= 1, 1 <= n <= 100000 and the sum of n in all T questions is not greater than 1000000.

Output
Print T lines. The i-th line contains your answer of Nvoenewr’s i-th question.

Sample Input
4
1
10
11
20
Sample Output
0
9
11
101

题目大意：给你一个k，输出第k大的回文串。

看着比较难，但是如果我们打表之后，就能发现一些规律。

对于个位数和10,11就特判一下然后对于首个数字不是1的k，它对应的回文串就是将首数字减一，在反转顺序贴到后面如k=523，则它对应的回文串就是42324，（注意，这种情况下，一定是将0-len-1位反转贴到后面，即中间要留一个）对于首个数字是1的k，是将它的首数字1直接抛弃，选取第2-len位如果第2位数字不是0，就是将2-len位反转后贴到后面如果第2位数字是0，先将0替换成9，再将2~len-1位反转后贴到后面（即这时中间要留一个）。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
int T,k;
string str;
signed main(){
	cin>>T;
	while(T--){
		cin>>str; int len=str.size();
		if(str=="10")	puts("9");
		else if(str=="11")	puts("11");
		else if(len==1)	cout<<char(str[0]-1)<<endl;
		else if(str[0]=='1'){
			if(str[1]=='0'){
				str[1]='9';
				string a=str.substr(1,len-1);//
				string b=str.substr(1,len-2);
				reverse(b.begin(),b.end());
				a+=b;
				cout<<a<<endl;
			}else{
				string a=str.substr(1,len-1);//
				string b=a;
				reverse(b.begin(),b.end());
				a=a+b;
				cout<<a<<endl;
			}
		}else{
			str[0]-=1;
			string a=str.substr(0,len-1);
			reverse(a.begin(),a.end());
			str+=a;
			cout<<str<<endl;
		}
	}
	return 0;
}