F. Сколько точек с пометкой

В той же таблице, что в классной задаче F, посчитайте количество точек $(x, y)$ с $0 \le x, y < 2^k$, пометка которых равна $c$.

Пометка равна $x \oplus y$, значит нужно количество пар с $x \oplus y = c$ в квадрате со стороной $2^k$.

Ответ короткий: если $c \ge 2^k$, таких пар нет вовсе — исключающее «или» двух чисел меньше $2^k$ само меньше $2^k$. Иначе для каждого из $2^k$ значений $x$ подходит ровно одно $y = x \oplus c$, и оно тоже меньше $2^k$. Значит, ответ равен $2^k$.

Это хороший пример того, как битовая задача сводится к одной строчке после правильного наблюдения. Проверять такие ответы стоит перебором на маленьких $k$ — там всё видно.

Первая строка содержит число $t$ ($1 \le t \le 10^5$).

Далее идут $t$ строк по два числа: $k$ ($0 \le k \le 60$) и $c$ ($0 \le c < 2^{62}$).

$t$ строк с ответами.