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