Ваня узнал про операцию ксор (исключающее или) и теперь нажимает эту кнопку на калькуляторе при каждом удобном случае. На экране пока число $$$a$$$, а Ваня хочет получить $$$b$$$. Правда, калькулятор у него вредный: ксорить он разрешает только с числами от нуля до $$$k$$$ включительно.
За один ход Ваня выбирает целое число $$$x$$$ ($$$0 \le x \le k$$$) и заменяет число $$$a$$$ на экране на $$$a \oplus x$$$. Здесь $$$\oplus$$$ обозначает ксор.
Чтобы вычислить ксор двух неотрицательных целых чисел, запишем их в двоичной системе счисления. Если записи имеют разную длину, дополним более короткую ведущими нулями слева. В каждом разряде результата поставим единицу, если биты двух чисел различаются, и ноль, если совпадают. Например, двоичные записи чисел пять и три — $$$101$$$ и $$$011$$$, поэтому их ксор равен $$$110$$$, то есть шести.
Помогите определить минимальное количество ходов, за которое Ваня может получить число $$$b$$$, либо сообщите, что это невозможно.
В первой строке находится целое число $$$t$$$ — количество наборов входных данных ($$$1 \le t \le 10^4$$$).
Каждая из следующих $$$t$$$ строк содержит три целых числа $$$a$$$, $$$b$$$ и $$$k$$$ ($$$0 \le a, b, k \le 10^9$$$).
Для каждого набора входных данных выведите одно целое число: минимальное количество ходов, необходимое, чтобы получить из $$$a$$$ число $$$b$$$, или $$$-1$$$, если это невозможно.
6 5 5 0 5 2 7 0 7 4 0 8 7 3 4 0 8 9 1
0 1 2 -1 -1 1
В первом наборе число $$$a$$$ уже равно $$$b$$$, поэтому ходы не нужны.
Во втором наборе выберем $$$x = 7$$$: $$$5 \oplus 7 = 2$$$.
В третьем наборе достаточно двух ходов: $$$0 \oplus 4 = 4$$$, затем $$$4 \oplus 3 = 7$$$. Одного хода недостаточно, поскольку $$$7 \gt k$$$.
В четвёртом наборе любое допустимое $$$x$$$ меньше восьми, поэтому ни один ход не может изменить бит, соответствующий восьми.
В пятом наборе допустимо только $$$x = 0$$$, что не изменяет $$$a$$$.
В шестом наборе выберем $$$x = 1$$$: $$$8 \oplus 1 = 9$$$.
| Название |
|---|


