Princess Celestia has allowed Discord to be released in order to reform him. Discord, of course, does not wish to be reformed. While loose, he secretly destroyed all of Twilight Sparkle's books on reforming spells. But only the books. The information is still there, locked behind his chaotic magic.

His chaotic magic created what is known as Mega String. To create this string, start by writing down the numbers 1, 2, 3, ..., and so on, and do this without putting any space between the numbers or digits.

So it would look like this: 12345678910111213141516....

However, for some reason, at that time, chaos dislikes the number 5.

So any number that contains 5 as a digit, anywhere, isn't included in the Mega String.

So the real Mega String looks like this:

1234678910111213141617...

and much later it looks like this:

.., 47, 48, 49, ...

...474849606162...

The question Twilight Sparkle needs to answer is, what is the digit that is at index K in the Mega String? Make sure to answer quickly, or else the information hidden by the Mega String will surely be lost to Twilight Sparkle.

The Mega String is 0-indexed.

Input format:

The first line is an integer T, which is the number of test cases to follow. The following T, line i+1 will contain an integer K_i.

Output format:

T lines are to be output, and on line i should be the digit at index K_i in the Mega String.

Sample Input:
5
0
1
2
3
4

Sample Output:
1
2
3
4
6

Limits:

1 <= T <= 10^5 and 0 <= K_i <= 10^18

Time: x5 my fastest Java solution.

Warning: Big Input Files