Multiple-of-Four Prefix Sequence

For each positive integer N, define A[N] as follows: A[N] is the smallest positive multiple of 4 whose decimal representation starts with N.

Concatenate A[1], A[2], A[3], ... in order to form an infinite string S. The sequence starts with 12, 20, 32, 4, 52, 60, ..., so S starts with 12203245260....

Given a positive integer K, find the K-th digit of S.

The input contains several test cases. Each test case consists of one positive integer K on a line.

K ≤ 10^15. The last line contains a single 0, which must not be processed.

For each test case, output the K-th digit of S on its own line.