Project Euler #40: Champernowne's constant

_{This problem is a programming version of Problem 40 from projecteuler.net}

An irrational decimal fraction is created by concatenating the positive integers:

It can be seen that the digit of the fractional part is 1.

If represents the digit of the fractional part, find the value of the following expression.

Input Format

First line contains that denotes the number of test cases. This is followed by lines, each containing an integers.

Constraints

Output Format

Print the answer corresponding to the test case.

Sample Input

1
1 2 3 4 5 6 7

Sample Output