C. XOR-расстояние
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны целые числа $$$a$$$, $$$b$$$, $$$r$$$. Найдите наименьшее значение величины $$$|({a \oplus x}) - ({b \oplus x})|$$$ по всем $$$0 \leq x \leq r$$$.

$$$\oplus$$$ это операция побитового исключающего ИЛИ, а $$$|y|$$$ — абсолютная величина числа $$$y$$$.

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

В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных содержит целые числа $$$a$$$, $$$b$$$, $$$r$$$ ($$$0 \le a, b, r \le 10^{18}$$$).

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

Для каждого набора входных данных выведите одно число — наименьшее возможное значение.

Пример
Входные данные
10
4 6 0
0 3 2
9 6 10
92 256 23
165 839 201
1 14 5
2 7 2
96549 34359 13851
853686404475946 283666553522252166 127929199446003072
735268590557942972 916721749674600979 895150420120690183
Выходные данные
2
1
1
164
542
5
3
37102
27934920819538516
104449824168870225
Примечание

В первом тесте $$$r = 0$$$, то есть $$$x$$$ точно равен $$$0$$$, поэтому ответ $$$|{4 \oplus 0} - {6 \oplus 0}| = |4 - 6| = 2$$$.

Во втором тесте:

  • при $$$x = 0$$$, $$$|{0 \oplus 0} - {3 \oplus 0}| = |0 - 3| = 3$$$;
  • при $$$x = 1$$$, $$$|{0 \oplus 1} - {3 \oplus 1}| = |1 - 2| = 1$$$;
  • при $$$x = 2$$$, $$$|{0 \oplus 2} - {3 \oplus 2}| = |2 - 1| = 1$$$.

Следовательно, ответ равен $$$1$$$.

В третьем тесте минимум достигается при $$$x = 1$$$.