4 1 s 128 MB

Given an infinite sequence A with A[N] (N>=1) being the smallest multiple of 4 that begins with N, concatenate digits of A[N] to create an infinite string S. Chuck Norris can do this for you in his spare time.

What is the Kth digit in S?

Specifically, sequence begins as 12,20,32,4,52,60,..., resulting in S="12203245260...".

Number of cases, each case contains positive integer $K$ $(K \leq 10^{15})$.

Last case is followed by the line containing a single zero.

For each test case, print the $K$th digit of S on separate line.

## Sample Input | ## Sample Output |
---|---|

1 7 15 0 | 1 4 9 |