http://codeforces.com/problemset/problem/1216/E1

E1. Numerical Sequence (easy version)

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

The only difference between the easy and the hard versions is the maximum value of k

.

You are given an infinite sequence of form "112123123412345…

" which consist of blocks of all consecutive positive integers written one after another. The first block consists of all numbers from 1 to 1, the second one — from 1 to 2, the third one — from 1 to 3, …, the i-th block consists of all numbers from 1 to i

.

So the first 56

elements of the sequence are "11212312341234512345612345671234567812345678912345678910". Elements of the sequence are numbered from one. For example, the 1-st element of the sequence is 1, the 3-rd element of the sequence is 2, the 20-th element of the sequence is 5, the 38-th element is 2, the 56-th element of the sequence is 0

.

Your task is to answer q

independent queries. In the i-th query you are given one integer ki. Calculate the digit at the position ki

of the sequence.

Input

The first line of the input contains one integer q

(1≤q≤500

) — the number of queries.

The i

-th of the following q lines contains one integer ki (1≤ki≤109)

— the description of the corresponding query.

Output

Print q

lines. In the i-th line print one digit xi (0≤xi≤9) — the answer to the query i, i.e. xi should be equal to the element at the position ki

of the sequence.

Examples

Input

Copy

5
1
3
20
38
56

Output

Copy

1
2
5
2
0

Input

Copy

4
2132
506
999999999
1000000000

Output

Copy

8
2
9
8

Note

Answers on queries from the first example are described in the problem statement.

题意：在数列中查找第i个数是多少。

//#include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <iostream>
    #include <algorithm>
    #include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <stdio.h>
    #include <queue>
    #include <stack>;
    #include <map>
    #include <set>
    #include <string.h>
    #include <sstream>
    #include <vector>
    #define ME(x , y) memset(x , y , sizeof(x))
    #define SF(n) scanf("%d" , &n)
    #define rep(i , n) for(int i = 0 ; i < n ; i ++)
    #define INF  0x3f3f3f3f
    #define mod 1000000007
    #define PI acos(-1)
    using namespace std;
    typedef long long ll ;
    int l[80009];
    int c[80009];
    int s[80009];
     
    int length(int x)
    {
        if(x >= 10000)
        {
            return 5 ;
        }
        else if(x >= 1000)
        {
            return 4 ;
        }
        else if(x >= 100)
            return 3 ;
        else if(x >= 10)
            return 2 ;
        else
            return 1 ;
    }
     
    void init()
    {
        for(int i = 1 ; i <= 60000 ; i++)
        {
            l[i] = length(i);
            c[i] = c[i-1]+l[i];
            s[i] = s[i-1]+c[i];
        }
    }
     
    int main()
    {
        int t ;
        init();
        scanf("%d" , &t);
        while(t--)
        {
            int n;
            scanf("%d" , &n);
            int index = lower_bound(s+1 , s+60000 , n) - s;
            n -= s[index-1];
            index = lower_bound(c+1 , c+index , n) - c;
            n -= c[index-1] ;
            n = l[index] - n ;
            while(n--)
            {
                index /= 10 ;
            }
            printf("%d\n" , index%10);
        }
     
     
        return 0;
    }