Problem Description

A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2...Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another. 

For example, the first 80 digits of the sequence are as follows: 

11212312341234512345612345671234567812345678912345678910123456789101112345678910

 

 

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647)

 

 

Output

There should be one output line per test case containing the digit located in the position i.

 

 

Sample Input

2 8 3

 

 

Sample Output

2 2

***************************************************************************************************************************

***************************************************************************************************************************

1 /* 2 一个数的位数可用log10((double)value)+1表示 3 a[]表示子串的长度，b[]表示到第i个子串时的总长度 4 */ 5 #include
       
         6 #include
        
          7 #include
         
           8 #include
          
            9 #include
           
            10 #include
            
             11 #include
             
              12 #define maxn 3200013 using namespace std;14 typedef long LL;15 unsigned int a[maxn],b[maxn];16 unsigned int n,m,j,k;17 unsigned int cas;18 int main()19 {20 a[0]=0;21 b[0]=0;22 a[1]=1;23 b[1]=1;24 LL i;25 for(i=2;i
              
               =remain)45 break;46 }47 unsigned int value_bit=1+log10((double)value);48 unsigned int position=remain-(sum-value_bit);49 unsigned int temp1=value;50 char* str = (char*)malloc(10*sizeof(char));51 unsigned int num=0;52 while(temp1)53 {54 unsigned int temp=temp1%10;55 str[num++]=temp+'0';56 temp1/=10;57 }58 str[num]='\0';59 if(position==value_bit)60 printf("%c\n",str[0]);61 else62 printf("%c\n",str[position-1]);63 64 }65 return 0;66 }