Виталий очень ленивый студент. И такое занятие, как посещение лекций, особенно если они не очень интересны и к тому же идут первыми парами, на которые приходится очень рано просыпаться, есть очень редким для него явлением. И вот он в который проспал лекцию по дискретной математике. В этот раз студенты должны были познакомиться с битовыми операциями, более конкретно - с операцией \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}.