无限数列

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

对于无限数列112123123412345123456123456712345678123456789123456789101234567891011,我们不难发现它的排列规律即1, 1-2, 1-3, 1-4, 1-5.....注意对于每一个数字认为它的每一位都是数列上的一个数,即对于10,我们认为它是1和0两个数。

 

问题:输出第这个数列中的第n个数是几。

Input

首先第一行输入一个整数T(T<=30)代表接下来有T个询问。

接下来输入T个询问,每一个询问仅包含一个正整数n(1<=n<=2^31-1)。

Output

对于每一个n,输出无限数列中第n个数是多少。

Sample Input

5
1
10
100
1000
10000

Sample Output

1
4
1
4
9

Hint

Source

Ransln