package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var t int
	if _, err := fmt.Fscan(reader, &t); err != nil {
		return
	}

	for tc := 0; tc < t; tc++ {
		var k, m int
		fmt.Fscan(reader, &k, &m)
		var s string
		fmt.Fscan(reader, &s)

		w := 0
		for i := 0; i < len(s); i++ {
			if s[i] == '1' {
				w++
			}
		}

		S := make([][]int, w+1)
		for i := 0; i <= w; i++ {
			S[i] = make([]int, w+1)
		}
		S[0][0] = 1
		for i := 1; i <= w; i++ {
			for j := 1; j <= i; j++ {
				S[i][j] = (S[i-1][j-1] + (j%2)*S[i-1][j]) % 2
			}
		}

		ans := 0
		for x := 0; x < m; x++ {
			fx := 0
			for r := 1; r <= w; r++ {
				if (x & (r - 1)) == (r - 1) {
					fx ^= S[w][r]
				}
			}
			if fx == 1 {
				ans ^= x
			}
		}
		fmt.Fprintln(writer, ans)
	}
}