Назовем битовой характеристикой целого положительного числа $$$n$$$ количество пар целых чисел $$$i$$$ и $$$j$$$ ($$$1 \le i \lt j$$$) таких, что $$$i \oplus j = n$$$$$$^{\text{∗}}$$$ и $$$i \lor j = n$$$$$$^{\text{†}}$$$.
Вычислите значение битовой характеристики данного числа $$$n$$$.
$$$^{\text{∗}}$$$$$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.
$$$^{\text{†}}$$$$$$\lor$$$ обозначает операцию побитового ИЛИ.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^9$$$) — число, для которого необходимо определить битовую характеристику.
Для каждого набора входных данных выведите единственное целое число — значение битовой характеристики числа $$$n$$$.
36842
1 0 3
В первом наборе входных данных существует только одна подходящая пара: $$$(2, 4)$$$.
Во втором наборе входных данных не существует ни одной подходящей пары.
В третьем наборе входных данных существуют следующие подходящие пары: $$$(2, 40)$$$, $$$(8, 34)$$$ и $$$(10, 32)$$$.
| BSUIR Open XIII: Школьный финал |
|---|
| Закончено |
