题目描述

只有ys知道ys是否处于困境之中

ys手里有一个数$n$，你的手里有数字$0$。

你可以对你手中的数字进行以下三种操作：

操作1：使数字$+1$

操作2：使数字$+2$

操作3：使数字$\times 2$

问你手里的数字最少需要进行多少次操作才能恰好和ys手里的相同。

输入

第一行输入一个数字$t$

接下来$t$行，每一行输入一个数字$n$。

输出

输出$t$行，数字$0$到$n$的最小操作次数。

样例

2
2
5

1
3

数据范围

$1\le t \le 10^5$

$0\le n \le 10^9$