Вадим захотел разобраться в бесконечной последовательности цифр, которая представляет из себя записанные подряд положительные целые числа от $$$1$$$ до бесконечности. То есть, эта последовательность имеет вид $$$123456789101112131415 \ldots$$$
Чтобы не смотреть в бесконечность, Вадим обрезал эту последовательность на $$$k$$$-й цифре и выкинул всё, что после неё. Таким образом, в последовательности осталось ровно $$$k$$$ цифр. Помогите ему найти сумму цифр в оставшейся последовательности.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ $$$(1 \le t \le 2 \cdot 10^4)$$$ — количество наборов входных данных. Далее следуют описания наборов входных данных.
В единственной строке каждого набора данных дано целое число $$$k$$$ — количество цифр в оставшейся последовательности $$$(1 \le k \le 10^{15})$$$.
Для каждого данного $$$k$$$ выведите сумму цифр в последовательности длины $$$k$$$.
6510132910000000001000000000000000
15 46 48 100 4366712386 4441049382716054
В первом примере оставшаяся последовательность будет равна $$$12345$$$.
Во втором примере оставшаяся последовательность будет равна $$$1234567891$$$.
В третьем примере оставшаяся последовательность будет равна $$$1234567891011$$$.
| Codeforces Round 1043 (Div. 3) |
|---|
| Закончено |
