Віталій дуже лінивий студент. І таке заняття, як відвідування лекцій, особливо якщо вони не досить цікаві та ще і є першими парами, на які доводиться досить рано вставати, є досить рідкісним для нього явищем. І ось він вкотре проспав лекцію із дискретної математики. Цього разу студенти повинні були ознайомитись із побітовими операціями, а детальніше із операцією \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 }i \textbf{b}, що \textbf{a }≤ \textbf{b }i \textbf{a OR b }= \textbf{c} для відповідного \textbf{c}.