package main

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

func main() {
	in := bufio.NewReaderSize(os.Stdin, 1<<20)
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	var T int
	fmt.Fscan(in, &T)
	for ; T > 0; T-- {
		var k, m int
		var b string
		fmt.Fscan(in, &k, &m)
		fmt.Fscan(in, &b)

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

		dp := make([]uint8, s+1)
		dp[0] = 1
		for i := 1; i <= s; i++ {
			ndp := make([]uint8, s+1)
			for j := 1; j <= i; j++ {
				v := dp[j-1]
				if j&1 == 1 {
					v ^= dp[j]
				}
				ndp[j] = v
			}
			dp = ndp
		}

		ans := 0
		for x := 0; x < m; x++ {
			var p uint8
			for t := 1; t <= s; t++ {
				if dp[t] == 1 && ((t-1)&^x) == 0 {
					p ^= 1
				}
			}
			if p == 1 {
				ans ^= x
			}
		}

		fmt.Fprintln(out, ans)
	}
}