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

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)

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

2

8

3

2

2

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

using namespace std;

typedef long long LL;

const LL MAXN = 2147483647;

const int Msize = 32000;

LL Sum[Msize], a[Msize];

void getS()

{

    Sum[1] = a[1] = 1;

    int i;

    for(i = 2; i < Msize; i++)

    {

        a[i] = a[i-1] + (int)log10((double)i)+1;

        Sum[i] = Sum[i-1] + a[i];

    }

    return;

}

LL Pow(LL a, LL b)

{

    LL ans = 1;

    while(b)

    {

        if(b&1)

            ans = ans*a;

        b>>=1;

        a = a*a;

    }

    return ans;

}

int main()

{

    getS();

    LL N;

    int T;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%I64d", &N);

        int i = 1, j, len, pos;

        while(N > Sum[i])

        {

            i++;

        }

        //第N位再i-1所代表的数字区

        pos = N - Sum[i-1];

        len = 0;

        for(j = 1; len < pos ; j++)

        {

            len += (int)log10(j*1.0) + 1;

        }

        //N为在i-1数字区中的第j-1个数中,len为这个数字的最后一位的位置

        int ans = (j-1)/Pow(10, len-pos)%10;

        printf("%d\n", ans);

    }

    return 0;

}