Problem H: Sequential Thinking

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...".

Input Format

Number of cases, each case contains positive integer K (K<=10^15). Last case is followed by the line containing a single zero.

Output Format

For each test case, print the Kth digit of S on separate line.

Sample Input

1
7
15
0

Sample Output

1
4
9

Darko Aleksic
ACPC 2012