This is the easy version of the problem. The difference between the versions is that in this version, the constraints on $t$, $k$, and $m$ are lower. You can hack only if you solved all versions of this problem.

A sequence $a$ of $n$ integers is called good if the following condition holds:

• Let $\text{cnt}_x$ be the number of occurrences of $x$ in sequence $a$. For all pairs $0 \le i < j < m$, at least one of the following has to be true: $\text{cnt}_i = 0$, $\text{cnt}_j = 0$, or $\text{cnt}_i \le \text{cnt}_j$. In other words, if both $i$ and $j$ are present in sequence $a$, then the number of occurrences of $i$ in $a$ is less than or equal to the number of occurrences of $j$ in $a$.

You are given integers $n$ and $m$. Calculate the value of the bitwise XOR of the median$^{\text{∗}}$ of all good sequences $a$ of length $n$ with $0\le a_i < m$.

Note that the value of $n$ can be very large, so you are given its binary representation instead.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 50$). The description of the test cases follows.

The first line of each test case contains two integers $k$ and $m$ ($1 \le k \le 200$, $1 \le m \le 500$) — the number of bits in $n$ and the upper bound on the elements in sequence $a$.

The second line of each test case contains a binary string of length $k$ — the binary representation of $n$ with no leading zeros.

It is guaranteed that the sum of $k$ over all test cases does not exceed $200$.

For each test case, output a single integer representing the bitwise XOR of the median of all good sequences $a$ of length $n$ where $0\le a_i < m$.