PONY8  Discord is at it again
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 0indexed.
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^18Time: x5 my fastest Java solution.
Warning: Big Input Files
hide comments
Francky:
20130127 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.).


Alex Anderson:
20130127 00:35:53
Hmm, might as well make the time limit larger, since I don't expect that actual bad solutions would pass.


Francky:
20130127 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.


Alex Anderson:
20130127 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)(æ›¾æ¯…æ˜†):
20130127 00:35:53
Server is very unstable, my same solution AC in range 0.31s0.36s


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20130127 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... 
Added by:  Alex Anderson 
Date:  20130125 
Time limit:  1s1.118s 
Source limit:  10000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  My own problem 