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

Tehran 2002, First Iran Nationwide Internet Programming Contest

寫了一整天

開始想先把1-1位數(shù)，1-2位數(shù)， 1-3位數(shù)，1-4位數(shù)的那個都算出來，然后減去
然后確定是那些中的
然后再確定是那一個的和中的
然后在確定數(shù)字
然后再求，
直接寫瘋了這次，寫了一天了
還是沒調(diào)出來
果斷刪掉
去網(wǎng)上找題解
直接用digit記錄123……n的數(shù)字個數(shù)，len記錄連續(xù)個這個12……n的總長
然后查找到這個數(shù)
然后在構(gòu)造出來，直接查就行了
不過速度沒法比

code