C2 为该问题的困难版。在困难版中，每组测试数据包含多个输入，同时 $n$ 的范围很大。

药学也是理学，火药也是药

"Phantom_73" 如是说

题目描述

"Phantom_73" 拿到了崭新的草稿纸，他迫不及待地开始在上面写数字。他从 $1$ 开始一直往下写，写到了 $n$。

他突发奇想，想算出写在纸上的每个数字的数字和等于多少。聪明的你帮他计算一下吧。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例数量。

接下来 $t$ 行，每行包含一个整数 $n$（$1 \leq n \leq 10^{15}$），表示 "Phantom_73" 从 $1$ 写到 $n$。

输出格式

对于每个测试用例，输出一个整数，表示最终结果。

样例输入输出

2
10
9999999999

46
450000000000