神“奇”的和 (II)

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

chY 忙碌了一天了,想放松一下自己,就找 ln 要来了一道题,由于 ln 不想打击 chY 的智商,所以随便丢了一道 easy 的题,题目是这样的:ln 给了 chY 好多的大整数 n ,让他计算每个 n 中所有奇数位(从右向左)上的数字的和。chY 看完之后不屑一笑,转身离去(其实是来求你帮忙了 QWQ)。

Input

第一行一个正整数 T(1 <= T <= 100),代表大整数 n 的数量;

 接下来有 T 行,每行有一个大整数 n 。(0<= n < = 2147483647)

Output

对每个大整数n输出一行整数,为所求答案。

Sample Input

3
0
12345
123456

Sample Output

0
9
12

Hint

样例 3:

123456 的和为 6 + 4 + 2 = 12

Source

行走的二叉树