1 s   128 MB

Description

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

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

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

Output

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

Sample Output

1
7
15
0

1
4
9


Source

The Alberta Collegiate Programming Contest (ACPC) 2012