L. Player 001
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The enigmatic owner of the Squid Games is searching for a new Front Man to take over his position and become Player 001. However, before he entrusts you with this role, he must test your intelligence.

Your first task seems simple:

Given an integer $$$ 1 \leq N \leq 10^{17} $$$, compute the sum of the digits of all numbers $$$ i $$$ for $$$ 1 \leq i \leq N $$$. That is, your answer should be:

$$$ \sum_{i=1}^{N} \text{sum_of_digits}(i) $$$

However, the owner finds this challenge too easy. To truly prove your worth, you must answer $$$ t $$$ consecutive test cases correctly.

Can you pass the test and claim the title of Player 001?

Input

The first line contains a single integer $$$ t $$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.

Each of the next $$$ t $$$ lines contains a single integer $$$ N $$$ $$$(1 \leq N \leq 10^{17})$$$.

Output

For each test case, output a single integer — the sum of the digits of all numbers $$$ i $$$ for $$$ 1 \leq i \leq N $$$.

Print each answer on a new line.

Example
Input
4
12
10
1
1254
Output
51
46
1
16125
Note

Example of Sum of Digits of a Number: sum_digits(10) = 1 + 0 = 1 sum_digits(123) = 1 + 2 + 3 = 6 And so on.

Explanation of a Test Case: Let's denote the function sum_of_digits as s. For Test Case 2, we calculate the sum of digits for all integers $$$i$$$ where $$$1 \leq i \leq 10$$$: $$$s(1) + s(2) + s(3) + s(4) + s(5) + s(6) + s(7) + s(8) + s(9) + s(10)= 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + (1 + 0)= 46$$$