Get Minimum Operations

Start from 0; each step either adds 1 or multiplies by 2. Find the minimum number of operations to reach each target value. The first part of the original text is missing; the set of operations is restored from the original description and the ADD_1 and MULTIPLY_2 examples.

输入格式

The first line contains n, followed by n values of k; full bounds from the original text: 1≤n≤10000, 0≤k≤10000000000000000.

输出格式

Output n lines with the minimum number of operations, in input order.

样例 1

输入：

2
5 3

输出：

4
3

样例 2

输入：

3
0 1 8

输出：

0
1
4

样例 3

输入：

3
7 16 31

输出：

5
5
9

样例说明

The outputs of the three public examples are, in order: 4 / 3; 0 / 1 / 4; 5 / 5 / 9. These answers have been checked by independent enumeration or direct simulation.