Vadim wanted to understand the infinite sequence of digits that consists of the positive integers written consecutively from (1) to infinity. That is, this sequence looks like (123456789101112131415 \ldots) To avoid looking into infinity, Vadim cut this sequence at the (k)-th digit and discarded everything after it. Thus, exactly (k) digits remained in the sequence. Help him find the sum of the digits in the remaining sequence. Each test consists of several test cases. The first line contains a single integer (t) ((1 \le t \le 2 \cdot 10^4)) — the number of test cases. The following lines describe the test cases. In a single line of each test case, there is an integer (k) — the number of digits in the remaining sequence ((1 \le k \le 10^{15})). For each given (k), output the sum of the digits in the sequence of length (k). In the first sample, the remaining sequence will be (12345). In the second sample, the remaining sequence will be (1234567891). In the third sample, the remaining sequence will be (1234567891011).