Задачи
Битовое уравнение
Битовое уравнение
Виталий очень ленивый студент. И такое занятие, как посещение лекций, особенно если они не очень интересны и к тому же идут первыми парами, на которые приходится очень рано просыпаться, есть очень редким для него явлением. И вот он в который проспал лекцию по дискретной математике. В этот раз студенты должны были познакомиться с битовыми операциями, более конкретно - с операцией \textbf{OR}.
Для того, чтобы проверить, как хорошо студенты усвоили материал, лектор решил дать им на следующей паре уравнение вида:
\textbf{a OR b} = \textbf{c}
Виталий очень быстро с ним справился. А сможете ли вы сделать это?
\InputFile
В первой строке задано число количество уравнений \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{100}). В последующих \textbf{t }сроках задано единственное число \textbf{c }(\textbf{1 }≤ \textbf{c }≤ \textbf{2^63 - 1}).
\OutputFile
Для каждого уравнения найти количество таких натуральных чисел \textbf{a }и \textbf{b}, что \textbf{a }≤ \textbf{b }и \textbf{a OR b }= \textbf{c} для соотвествующего \textbf{c}.
Входные данные #1
1 1
Выходные данные #1
1