← 返回题目列表

Codeforces · 2132/D

D. 从 1 到无穷大

中文机器翻译题面 查看原题

Vadim 想要理解由从 $$$1$$$ 到无穷大连续写入的正整数组成的无限数字序列。也就是说,这个序列看起来像 $$$123456789101112131415 \ldots$$$

为了避免查看无穷大,Vadim 在第 $$$k$$$ 位处剪切了该序列,并丢弃了其后的所有内容。因此,序列中恰好保留了 $$$k$$$ 个数字。帮助他找到剩余序列中的数字之和。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 2 \cdot 10^4)$$$ — 测试用例的数量。以下几行描述了测试用例。

在每个测试用例的一行中,有一个整数 $$$k$$$ — 剩余序列 $$$(1 \le k \le 10^{15})$$$ 中的位数。

输出

对于每个给定的$$$k$$$,输出长度为$$$k$$$的序列中的数字之和。

示例

输入
复制

6
5
10
13
29
1000000000
1000000000000000

输出
复制

15
46
48
100
4366712386
4441049382716054

注意

在第一个示例中,剩余序列将为 $$$12345$$$。

在第二个示例中,剩余序列将为 $$$1234567891$$$。

在第三个示例中,剩余序列将为 $$$1234567891011$$$。