Для заданного целого числа найдите количество таких целых чисел , которые удовлетворяют условиям:
где — битовый XOR оператор.
Имеются запросов, каждый из которых содержит целое число . Для каждого запроса выведите общее количество значений , удовлетворяющих условиям выше.
Первая строка содержит число запросов . Каждая из следующих строк содержит значение .
Для каждого теста выведите в отдельной строке количество значений , удовлетворяющих приведенным условиям.