题目描述

在魔法学院，每位学徒都需要完成一项数字魔法考核。考核规则如下：

你面前有一个魔法水晶，初始显示数字 $0$。考核目标是让水晶显示指定的数字 $n$。

作为学徒，你掌握两种基础魔法：

1. $+1$ 魔法：使水晶上的数字增加 $1$
2. $×2$ 魔法：使水晶上的数字变为原来的 $2$ 倍

每次施展魔法都会消耗你的魔力，你的目标是通过搜索最优的操作序列，用最少的魔法次数让水晶显示数字 $n$。

请计算从 $0$ 开始，到达目标数字 $n$ 所需要的最少魔法次数。

输入格式

第一行一个整数 $T$（$1 ≤ T ≤ 10^3$），表示测试数据组数。

接下来T行，每行一个整数 $n_i$（$0 ≤ n_i ≤ 10^6$），表示第 $i$ 轮考核的目标数字。

输出格式

输出 $T$ 行，每行一个整数，表示对应轮次从 $0$ 到 $n_i$ 的最少魔法次数。

样例

3
0
4
5

0
3
4