B'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 k_i . Calculate the digit at the position k_i of the sequence. 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 k_i (1 <= k_i <= 10^9) -- the description of the corresponding query. Print q lines. In the i -th line print one digit x_i (0 <= x_i <= 9) -- the answer to the query i , i.e. x_i should be equal to the element at the position k_i of the sequence. Answers on queries from the first example are described in the problem statement. '...