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

---

hide comments

	Francky: 2013-01-27 00:41:28 @Alex : thanks for that, we just have to remember that python have a start up time for interpreter (0.03s for py2 on pyramid and quite 0.5s for py3), this time (for doing "nothing") is counted, unlike the compilation time for C users (e.g.). Even for small data case, I let quite the same time to avoid trouble with that. Thanks again for your attention.
	Alex Anderson: 2013-01-27 00:35:53 Hmm, might as well make the time limit larger, since I don't expect that actual bad solutions would pass. Francky - it seems like your Python 2.7 submission almost made it with the strict limit. It only time out (originally) on the first test case, all the rest were up to speed. But you are correct, so I've increased the time limit to x5 my Java solution per test case, and I've rerun the submissions which had timed out. Last edit: 2013-01-27 00:35:33
	Francky: 2013-01-27 00:35:53 It is very I/O related, why time limit so strict ? It avoid good solutions in Python ! Any bad solution with a fast language will get TLE even with twice time limit. I don't say it's impossible in python, just need some black magic power for I/O, and I don't know them, so few people know them (in fact only one here at my knowledge). But, it's a good problem, it was nice to solve it.
	Alex Anderson: 2013-01-27 00:35:53 I think it has always been that way - that for problems with a lot of input or processing, the variance if probably because of how spoj manages running its judge.
	(Tjandra Satria Gunawan)(曾毅昆): 2013-01-27 00:35:53 Server is very unstable, my same solution AC in range 0.31s-0.36s EDIT: seems that python is much slower than JAVA :-P :Alex: yes, I used the fastest input and output that I know of for Java. Just because. Last edit: 2013-01-26 00:49:04
	(Tjandra Satria Gunawan)(曾毅昆): 2013-01-27 00:35:53 Very nice problem :-D I like the problem that using pyramid cluster... It can show more accurate running time than using cube cluster...