Бараш наконец-то смог уединиться и тут же взялся за сочинение долгожданного стихотворения. Его новый стих содержит $$$2^n$$$ строк, в которых $$$a_1, a_2, a_3, \ldots, a_{2^n}$$$ слогов соответственно.
Поэты привыкли к одностишьям, двустишьям, четверостишьям и т.д., поэтому прекрасно работают со степенями двойки. Бараш построил над своим стихом полное бинарное дерево, записав в листья значения $$$a_1, a_2, \ldots, a_{2^n}$$$. Напомним, что полным бинарным деревом называется бинарное дерево, каждая вершина которого имеет 0 или 2 сына.
Согласно новой литературной теории Бараша, стих шедевральный, если все $$$a_i$$$ в полном бинарном дереве попарно различны. Эта гениальная идея пришла к нему довольно поздно, поэтому было проще дописать стих и потом немного подправить его, чем переписывать с нуля.
Бараш выбрал для себя действие, которым будет редактировать стих. Он рассматривает построенное дерево, удаляет одно из поддеревьев и на его место копирует любое другое поддерево (возможно, другого размера), заменив все $$$a_i$$$ из поддерева на $$$a_i \oplus k$$$. Для лучшего понимания ниже дана иллюстрация одного редактирования с $$$k=4$$$.
Бараш хочет как можно скорее прочитать шедевральный стих друзьям. Помогите ему найти минимальное число редактирований или сообщите, что сделать стих шедевральным невозможно.
В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора даны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 20$$$, $$$0 \le k \le 2^{31} - 1$$$).
Во второй строке каждого набора даны $$$2^n$$$ целых чисел $$$a_1, a_2, \ldots, a_{2^n}$$$ ($$$0 \le a_i \le 2^{31} - 1$$$) — количества слогов.
Гарантируется, что сумма $$$2^{n}$$$ по всем наборам входных данных не превосходит $$$2^{20}$$$.
Для каждого набора входных данных выведите минимальное количество редактирований или $$$-1$$$, если получить шедевральный стих невозможно.
83 42 7 3 9 2 3 5 42 41 2 3 42 12 3 2 32 02 2 1 12 10 0 0 02 13 3 3 11 132 42 10 1 0 0
102-12102
Первый пример совпадает с картинкой из условия.
