Последний контест, проведённый на любимой Джонни платформе по спортивному программированию, был встречен довольно позитивно. Однако, рейтинг Джонни снова упал! Он думает, что хотя задачи были неплохие, они не показывают истинный уровень участников.
Теперь мальчик смотрит на рейтинги соседних участников, записанные в двоичной системе счисления. Он считает, что чем больше эти рейтинги различаются, тем более нечестно, что эти участники расположены на соседних позициях. Он определяет различие между двумя числами как количество позиций битов, на которых одно из чисел содержит ноль, а другое — единицу (мы считаем, что числа дополнены ведущими нулями до одинаковой длины). Например, различие между числами \(5 = 101_2\) и \(14 = 1110_2\) равно \(3\), так как \(0101\) и \(1110\) отличаются в \(3\) позициях. Джонни определяет нечестность контеста как сумму таких различий для всех пар соседних участников.
Джонни только что прислал вам последовательность рейтингов и хочет, чтобы вы вычислили нечестность контеста. Вы заметили, что вы получили последовательные целые числа от \(0\) до \(n\). Это странно, но мальчик упорно твердит, что все правильно. Поэтому, помогите ему и вычислите желаемую нечестность для полученной последовательности чисел.
Выходные данные
Выведите \(t\) строк. Для каждого набора входных данных, вы должны вывести одну строку, содержащую одно целое число — нечестность контеста, если последовательность рейтингов равна \(0\), \(1\), ..., \(n - 1\), \(n\).
Примечание
Для \(n = 5\), мы вычисляем нечестность следующей последовательности (числа от \(0\) до \(5\), записанные в двоичной системе счисления и дополненные ведущими нулями до одинаковой длины):
- \(000\)
- \(001\)
- \(010\)
- \(011\)
- \(100\)
- \(101\)
Различия равны \(1\), \(2\), \(1\), \(3\), \(1\), соответственно. Поэтому, нечестность равна \(1 + 2 + 1 + 3 + 1 = 8\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5
7
11
1
2000000000000
|
8
11
19
1
3999999999987
|