A*B 1.0

时间限制：1000ms

空间限制：256MB

题目背景

ICDAT最近被计算机系统基础这门课折磨得心力交瘁，不过他也遇到了许多有意思的问题。例如：

计基课中，ICDAT知道了对于计算机而言，整数的乘法运算比移位和加法等运算所用时间长，通常一次乘法运算需要多个时钟周期，而一次移位、加法和减法等运算只要一个或更少的时钟周期，因此，编译器在处理变量与常数相乘时，往往以移位、加法和减法的组合运算来代替乘法运算。

举个例子，对于一个给定的数 $20$ ,若我们要计算表达式 $x*20$ ，可以利用 $20=16+4=2^4+2^2$，将 $x*20$ 转换为 $(x<<4)+(x<<2)$ ，这样，一次乘法转换成了两次移位和一次加法。

说明：$<<$ 为二进制数左移，$(x<<4)$ 和 $(x<<2)$ 分别代表将 $x$ 转换为二进制数之后，向左移动 $4$ 位与 $2$ 位，对应着十进制数 $x$ 完成 $x*2^4$ 和 $x*2^2$ 两个操作，最后再将两个结果相加就可以得到我们要的最终结果。

再或者，给定的数为 $19$ ，若我们要计算表达式 $x*19$ ，可以利用 $19=16+2+1=2^4+2^1+2^0$ 同样地进行转换。（ 特别地，在本题中，对于 $x*2^0$ 而言，我们也认为必须执行一次 $(x<<0)$ 这样的移位操作。）

题目描述

在1.0版本中，假设无论移动多少位所花费的时间是固定的，均为 $1$ ，而加法操作所花费的时间也是固定的，均为 $100$ 。现在需要你模拟计算机内部的运算逻辑，对于给定的任意一个乘数 $a$ ，寻找出一个合适的拆分方法，使得它与其它数相乘时运算时间最快。

注意：只允许进行左移和加法两种运算的组合

输入格式

输入第一行，包含 $1$ 个整数 $t$ ，代表询问次数 。

接下来 $t$ 行，每行包含一个整数 $a$ ，代表乘数。

输出格式

输出一个整数，代表最快的运算时间。

样例输入1

2
20
19

样例输出1

102
203

样例1解释

如背景中解释的，对于20，两次移位，一次加法，总运算时间为102。

对于19，三次移位，两次加法，总运算时间为203.

可以证明这为最优解。

数据范围及约定

对于 $100\%$ 的数据，$1 \le a \le 1e9$ ，$1 \le t \le 1e5$# problem A*B 1.0