Для заданного целого x найти количество таких a, удовлетворяющих условию:

• a xor x > x

• 0 < a < x

где a и x - целые, xor - битовый XOR оператор.

Имеются q запросов, каждый из которых содержит целое число x. Для каждого запроса выведите общее количество значений a, удовлетворяющих условиям выше.

Входные данные

Первая строка содержит число запросов q (1 ≤ q ≤ 105). Каждая из следующих q строк содержит значение x (1 ≤ x ≤ 1010).

Выходные данные

Для каждого теста выведите в отдельной строке количество значений a, удовлетворяющих приведенным условиям.