На числовой прямой в точке с координатой \(0\) сидит кузнечик. За одно действие он может выбрать любое целое неотрицательное число \(k\) и прыгнуть влево или вправо на расстояние \(2^k\).
Помогите кузнечику определить, какое минимальное количество действий ему понадобится выполнить, чтобы из точки с координатой \(0\) попасть в точку с координатой \(x\).
Формат входных данных
В первой строке дано одно целое число \(t\) — количество наборов входных данных (\(1 \le t \le 100\,000\)).
Каждый набор входных данных состоит из единственной строки, в которой дано целое число \(x\) — координата точки, в которую хочет попасть кузнечик (\(-10^{18} \le x \le 10^{18}\)).
Формат выходных данных
Для каждого набора входных данных выведите одно целое число — минимальное количество действий, которое кузнечику понадобится совершить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1
-4
0
-7
239
|
1
1
0
2
3
|