This is the hard version of the problem. The difference between the versions is that in this version, the constraints on $t$, $k$, and $m$ are higher. 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 \lt j \lt 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 \lt m$.

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

$^{\text{∗}}$The median of a sequence $a$ of length $n$ is defined as the $\left\lfloor\frac{n + 1}{2}\right\rfloor$-th smallest value in the sequence.

Input

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

The first line of each test case contains two integers $k$ and $m$ ($1 \le k \le 2 \cdot 10^5$, $1 \le m \le 10^9$) — 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 $2\cdot 10^5$.

Output

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 \lt m$.

Note

In the first example, $n = 10_2 = 2$ and $m = 3$. All possible sequences with elements less than $m$ are: $[0, 0]$, $[0, 1]$, $[0, 2]$, $[1, 0]$, $[1, 1]$, $[1, 2]$, $[2, 0]$, $[2, 1]$, $[2, 2]$. All of them are good, so the answer is: $0 \oplus 0 \oplus 0 \oplus 0 \oplus 1 \oplus 1 \oplus 0 \oplus 1 \oplus 2 = 3$.

In the second example, $n = 11_2 = 3$ and $m = 3$. Some good sequences are $[2, 2, 2]$, $[1, 0, 1]$, and $[2, 0, 1]$. However, a sequence $[2, 0, 0]$ is not good, because $\text{cnt}_0 = 2$, $\text{cnt}_2 = 1$. Therefore, if we set $i = 0$ and $j = 2$, $i \lt j$ holds, but $\text{cnt}_i \le \text{cnt}_j$ does not.