```go
package main

import (
	"bytes"
	"io"
	"math/bits"
	"os"
	"strconv"
)

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) nextInt() int {
	for fs.idx < fs.n && (fs.data[fs.idx] < '0' || fs.data[fs.idx] > '9') {
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n && fs.data[fs.idx] >= '0' && fs.data[fs.idx] <= '9' {
		val = val*10 + int(fs.data[fs.idx]-'0')
		fs.idx++
	}
	return val
}

func (fs *FastScanner) nextString() string {
	for fs.idx < fs.n && fs.data[fs.idx] <= ' ' {
		fs.idx++
	}
	start := fs.idx
	for fs.idx < fs.n && fs.data[fs.idx] > ' ' {
		fs.idx++
	}
	return string(fs.data[start:fs.idx])
}

type Pre struct {
	d          uint
	P          uint64
	fullParity uint8
	fullXor    uint64
	prefParity []uint8
	prefXor    []uint64
}

func xorUpto(n uint64) uint64 {
	switch n & 3 {
	case 0:
		return n
	case 1:
		return 1
	case 2:
		return n + 1
	default:
		return 0
	}
}

func build(p int) *Pre {
	d := bits.Len(uint(p - 1))
	P := 1 << d
	a := make([]uint8, P)
	for k := 0; k < p; k++ {
		if ((p-k-1)&(k>>1)) == 0 {
			a[k] = 1
		}
	}
	for bit := 1; bit < P; bit <<= 1 {
		step := bit << 1
		for start := 0; start < P; start += step {
			for i := start + bit; i < start+step; i++ {
				a[i] ^= a[i-bit]
			}
		}
	}
	prefParity := make([]uint8, P+1)
	prefXor := make([]uint64, P+1)
	for i := 0; i < P; i++ {
		prefParity[i+1] = prefParity[i] ^ a[i]
		prefXor[i+1] = prefXor[i]
		if a[i] == 1 {
			prefXor[i+1] ^= uint64(i)
		}
	}
	return &Pre{
		d:          uint(d),
		P:          uint64(P),
		fullParity: prefParity[P],
		fullXor:    prefXor[P],
		prefParity: prefParity,
		prefXor:    prefXor,
	}
}

func main() {
	fs := NewFastScanner()
	t := fs.nextInt()
	cache := make(map[int]*Pre)
	var out bytes.Buffer
	for ; t > 0; t-- {
		_ = fs.nextInt()
		m := uint64(fs.nextInt())
		s := fs.nextString()
		p := 0
		for i := 0; i < len(s); i++ {
			if s[i] == '1' {
				p++
			}
		}
		pre := cache[p]
		if pre == nil {
			pre = build(p)
			cache[p] = pre
		}
		cnt := m / pre.P
		rem := int(m % pre.P)
		var ans uint64
		if cnt&1 == 1 {
			ans ^= pre.fullXor
		}
		if pre.fullParity == 1 && cnt > 0 {
			ans ^= xorUpto(cnt-1) << pre.d
		}
		ans ^= pre.prefXor[rem]
		if pre.prefParity[rem] == 1 {
			ans ^= cnt << pre.d
		}
		out.WriteString(strconv.FormatUint(ans, 10))
		out.WriteByte('\n')
	}
	os.Stdout.Write(out.Bytes())
}
```