F1. Xor медиан (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Отличие между версиями заключается в том, что в этой версии ограничения на $$$t$$$, $$$k$$$ и $$$m$$$ ниже. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Последовательность $$$a$$$ из $$$n$$$ целых чисел называется хорошей, если выполняется следующее условие:

  • Пусть $$$\text{cnt}_x$$$ — количество вхождений $$$x$$$ в последовательность $$$a$$$. Для всех пар $$$0 \le i < j < m$$$, по крайней мере одно из следующих условий должно быть истинным: $$$\text{cnt}_i = 0$$$, $$$\text{cnt}_j = 0$$$ или $$$\text{cnt}_i \le \text{cnt}_j$$$. Другими словами, если и $$$i$$$, и $$$j$$$ присутствуют в последовательности $$$a$$$, то число вхождений $$$i$$$ в $$$a$$$ меньше или равно числу вхождений $$$j$$$ в $$$a$$$.

Вам даны целые числа $$$n$$$ и $$$m$$$. Вычислите значение побитового XOR медиан$$$^{\text{∗}}$$$ всех хороших последовательностей $$$a$$$ длины $$$n$$$, таких, что $$$0\le a_i < m$$$.

Обратите внимание, что значение $$$n$$$ может быть очень большим, поэтому вместо него вам даётся его двоичное представление.

$$$^{\text{∗}}$$$Медиана последовательности $$$a$$$ длины $$$n$$$ определяется как $$$\left\lfloor\frac{n + 1}{2}\right\rfloor$$$-е наименьшее значение в последовательности.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 50$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$k$$$ и $$$m$$$ ($$$1 \le k \le 200$$$, $$$1 \le m \le 500$$$) — количество битов в $$$n$$$ и верхнюю границу элементов в последовательности $$$a$$$.

Вторая строка каждого набора входных данных содержит бинарную строку длины $$$k$$$ — двоичное представление $$$n$$$ без ведущих нулей.

Гарантируется, что сумма значений $$$k$$$ по всем наборам входных данных не превосходит $$$200$$$.

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

Для каждого набора входных данных выведите одно целое число — побитовый XOR медиан всех хороших последовательностей $$$a$$$ длины $$$n$$$, где $$$0\le a_i < m$$$

Пример
Входные данные
6
2 3
10
2 3
11
5 1
11101
7 9
1101011
17 34
11001010001010010
1 500
1
Выходные данные
3
2
0
8
32
0
Примечание

В первом наборе входных данных, $$$n = 10_2 = 2$$$ и $$$m = 3$$$. Существуют такие последовательности с элементами меньше $$$m$$$: $$$[0, 0]$$$, $$$[0, 1]$$$, $$$[0, 2]$$$, $$$[1, 0]$$$, $$$[1, 1]$$$, $$$[1, 2]$$$, $$$[2, 0]$$$, $$$[2, 1]$$$, $$$[2, 2]$$$. Все они являются хорошими, поэтому ответ равен $$$0 \oplus 0 \oplus 0 \oplus 0 \oplus 1 \oplus 1 \oplus 0 \oplus 1 \oplus 2 = 3$$$.

Во втором наборе входных данных, $$$n = 11_2 = 3$$$ и $$$m = 3$$$. Некоторыми хорошими последовательностями являются $$$[2, 2, 2]$$$, $$$[1, 0, 1]$$$, и $$$[2, 0, 1]$$$. Однако последовательность $$$[2, 0, 0]$$$ не является хорошей, потому что $$$\text{cnt}_0 = 2$$$, $$$\text{cnt}_2 = 1$$$. Следовательно, если мы выберем $$$i = 0$$$ и $$$j = 2$$$, то $$$i < j$$$ выполняется, а $$$\text{cnt}_i \le \text{cnt}_j$$$ неверно.