Param is a god boy. He likes to do "tafreeh" with Elpoep. Elpoep are imaginary beings living in Ruprimah. His habit started with 0 nuf per day where nuf is the measure of enjoyment he gets out of his habit. Over the years the nuf value per day has increased as he is joined by some other scitanul (people like Param) of the same league. The measurement has gone way beyond a PC can handle, so they decided a coding mechanism. The nuf value mapped to n is x where x is given by the following algorithm.

Assume all non negative numbers are arranged in ascending order in a string named str

x = str[n-1]

where str = "1234567891011121314....."

INPUT

First line contains an integer T where T is the number of test cases.

Next T lines contain a single integer N.

OUTPUT

Print the value of x for each N in a newline.

CONSTRAINTS

1 <= T <= 2*1000000

1 <= N <= 2^31