H君有一天出门的时候也许是因为过于疲惫，不幸追尾了一辆黑色高级轿车，车主提出的和解条件是......解答一个数论难题！H君一秒钟就搞到了答案，但是想要保护后辈的您决定帮H君回答这个问题：
车主定义了一个函数 $f(x)$ 表示正整数 $x$ 的各数位之和，举例来说，$f(114514) = 1+1+4+5+1+4=16$。
现在将有 $q$ 次询问，每次询问给出一个数 $n$ ，您需要回答 $n$ 的约数中有多少个数 $x$ 满足 $f(x)=\left\lfloor \frac{x}{2}\right\rfloor$ 。
第一行一个数 $q$ ，表示询问次数。
接下来 $q$ 行，每行一个数 $n$。
数据范围：
$1\leq n \leq10^{18}, 1 \leq q \leq 10^5$ 。
共 $q$ 行，每一行为给出的 $n$ 的约数中满足条件的数的个数。
11 1 2 3 4 5 6 7 8 9 10 1145141919810
0 0 0 0 0 0 0 0 0 0 1
样例解释 1：
对于数字 $1,2,3...10$ ，可以计算发现它们都不满足条件，所以 $n=1,2,3...10$ 时答案都是 $0$ 。
Comet OJ