Let us define a few functions over natural numbers,
$F(n) =$ sum of odd digits in decimal representation of n.
For example, $F(123) = 1+3 = 4$ and $F(15423) = 1+5+3 = 9$.

$G(n) = \sum\limits_{d|n} f(d)$,
that is, sum of $F(d)$ over all factors d of n.
For example, $G(10) = F(1) + F(2) + F(5) + F(10) = 7$.

Input:
First line of the input contains 1 integers, Q, representing number of queries. Next Q line contains 1 integers each, representing n.

Output:
N lines, each line containing 1 integers, representing $G(n)$.

Constraints:
$1 \le Q \le 10^6$
$1 \le N \le 10^6$