Description

Concatenate all positive integers greater than 0 in a sequence to form an infinitely long number, i.e., 12345678910111213141516.... What is the digit at the nth position of this number?

Input Format

First line: A single integer T indicating the number of queries (2 ≤ T ≤ 100000). Lines 2 to n+1: Each line contains a single integer, representing the query for n (1 ≤ n ≤ 10^9).

Output Format

Output T lines in total, each corresponding to the answer for the respective query.

```input1 3 3 10 21 ``` ```output1 3 1 5 ``` ## Hint

【Data Range】

For 4% of the data, 2≤T≤10, 1≤n≤100;

For 40% of the data, 2≤T≤500, 1≤n≤50000;

For 100% of the data, 2≤T≤100000, 1≤n≤10^9;

Source

CodesOnline