Vanya got an important task — he should enumerate books in the library and label each book with its number. Each of the *n* books should be assigned with a number from 1 to *n*. Naturally, distinct books should be assigned distinct numbers.

Vanya wants to know how many digits he will have to write down as he labels the books.
The first line contains integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">9</sup>) — the number of books in the library.
# coding=utf-8
t=int(input())
for i in range(t):
    x=int(input())#盒子里的金币数
    s=0#詹博士的金币数
    turn=1#表示詹博士的回合，trun=0对手回合    
    while x>0:
        if x%2==1:#盒子金币x为奇数时都只能拿一个
           if turn==1:
               s+=1
               turn=0
           else:
               turn=1
           x-=1#无论是谁的回合，盒子内的金币都会减少（一下类似语句同作用）
        else:
           if x%4==0:#x为偶数且为4 的倍数
               if x//4==1:#只剩下4个
                   if turn==1:
                      s+=x//2
                      turn=0
                   else:
                      turn=1
                   x=x//2
               else:#处理x为4的倍数但不等于4的情况
                   if turn==1:
                       s+=1
                       turn=0
                   else:#处理x为2的倍数但不为4的倍数的情况
                       turn=1
                   x-=1
           else:
               if turn==1:
                   s+=x//2
                   turn=0
               else:
                   turn=1
               x=x//2
    print(s)

    	 	  			  	  	   	 	 			  	