Бітове рівняння
Віталій дуже лінивий студент. І таке заняття, як відвідування лекцій, особливо якщо вони не досить цікаві та ще і є першими парами, на які доводиться досить рано вставати, є досить рідкісним для нього явищем. І ось він вкотре проспав лекцію із дискретної математики. Цього разу студенти повинні були ознайомитись із побітовими операціями, а детальніше із операцією OR.
Для того, щоб перевірити, як добре студенти засвоїли матеріал, лектор вирішив задати їм на наступній парі рівняння виду:
a OR b = c
Віталій дуже швидко із ним впорався. А чи зможете зробити це ви?
Вхідні дані
У першому рядку задано число кількість рівнянь t (1 ≤ t ≤ 100). У наступних t рядках задається єдине число c (1 ≤ c ≤ 2^63 - 1).
Вихідні дані
Для кожного рівняння знайти кількість таких натуральних чисел a i b, що a ≤ b i a OR b = c для відповідного c.