Given an infinite sequence A with A[N] (N ≥ 1) be- ing 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 K-th 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 ≤ 1015). Last case is followed by the line con- taining a single zero. Output For each test case, print the K-th digit of S on separate line. Sample Input 1 7 15 0 Sample Output 1 4 9