Cho một số nguyên ~n~, hãy đếm tổng số chữ số ~1~ xuất hiện trong tất cả các số nguyên không âm nhỏ hơn hoặc bằng ~n~.

Input

Dòng đầu tiên gồm số nguyên dương ~t~ ~(1 \le t \le 1000)~ - số lượng testcase:

Trong mỗi testcase có dạng như sau:

• Một dòng duy nhất là số nguyên dương ~n~ ~(1 \le n \le 10^9)~

Output

Một dòng duy nhất là kết quả bài toán

Sample Input

1
13

Sample Output

6