package main

import (
	"bufio"
	"os"
	"strconv"
)

const M1 = 1000000007
const M2 = 1000000009
const B1 = 313
const B2 = 317

var pow1 []uint32
var pow2 []uint32

func init() {
	pow1 = make([]uint32, 5000005)
	pow2 = make([]uint32, 5000005)
	pow1[0] = 1
	pow2[0] = 1
	for i := 1; i <= 5000000; i++ {
		pow1[i] = uint32((uint64(pow1[i-1]) * B1) % M1)
		pow2[i] = uint32((uint64(pow2[i-1]) * B2) % M2)
	}
}

func extGCD(a, b int) (int, int, int) {
	if b == 0 {
		return a, 1, 0
	}
	d1, x1, y1 := extGCD(b, a%b)
	return d1, y1, x1 - y1*(a/b)
}

func can_form(m, a, b int) bool {
	d, x, y := extGCD(a, b)
	if m%d != 0 {
		return false
	}
	u0 := x * (m / d)
	v0 := y * (m / d)
	stepU := b / d
	stepV := a / d

	var minK, maxK int
	if u0 >= 0 {
		minK = -(u0 / stepU)
	} else {
		minK = (-u0 + stepU - 1) / stepU
	}

	if v0 >= 0 {
		maxK = v0 / stepV
	} else {
		maxK = -(-v0 + stepV - 1) / stepV
	}

	return minK <= maxK
}

func solve() {
	scanner := bufio.NewScanner(os.Stdin)
	buf := make([]byte, 1024*1024*10)
	scanner.Buffer(buf, 1024*1024*20)
	scanner.Split(bufio.ScanWords)

	if !scanner.Scan() {
		return
	}
	T, _ := strconv.Atoi(scanner.Text())

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	for t_case := 0; t_case < T; t_case++ {
		scanner.Scan()
		n, _ := strconv.Atoi(scanner.Text())

		scanner.Scan()
		m, _ := strconv.Atoi(scanner.Text())

		scanner.Scan()
		s := scanner.Text()

		scanner.Scan()
		t := scanner.Text()

		hashS1 := make([]uint32, n+1)
		hashS2 := make([]uint32, n+1)
		for i := 0; i < n; i++ {
			hashS1[i+1] = uint32((uint64(hashS1[i])*B1 + uint64(s[i])) % M1)
			hashS2[i+1] = uint32((uint64(hashS2[i])*B2 + uint64(s[i])) % M2)
		}

		hashT1 := make([]uint32, m+1)
		hashT2 := make([]uint32, m+1)
		for i := 0; i < m; i++ {
			hashT1[i+1] = uint32((uint64(hashT1[i])*B1 + uint64(t[i])) % M1)
			hashT2[i+1] = uint32((uint64(hashT2[i])*B2 + uint64(t[i])) % M2)
		}

		getHashS := func(l, r int) uint64 {
			length := r - l
			h1 := (uint64(hashS1[r]) + M1 - (uint64(hashS1[l])*uint64(pow1[length]))%M1) % M1
			h2 := (uint64(hashS2[r]) + M2 - (uint64(hashS2[l])*uint64(pow2[length]))%M2) % M2
			return (h1 << 32) | h2
		}

		getHashT := func(l, r int) uint64 {
			length := r - l
			h1 := (uint64(hashT1[r]) + M1 - (uint64(hashT1[l])*uint64(pow1[length]))%M1) % M1
			h2 := (uint64(hashT2[r]) + M2 - (uint64(hashT2[l])*uint64(pow2[length]))%M2) % M2
			return (h1 << 32) | h2
		}

		commutes := func(i int) bool {
			return getHashS(0, n-i) == getHashS(i, n) && getHashS(n-i, n) == getHashS(0, i)
		}

		isPrefix := true
		for j := 0; j < m; j++ {
			if t[j] != s[j%n] {
				isPrefix = false
				break
			}
		}

		ans := make([]byte, n-1)

		for i := 1; i < n; i++ {
			a := i
			b := n - i
			if commutes(i) {
				if isPrefix && can_form(m, a, b) {
					ans[i-1] = '1'
				} else {
					ans[i-1] = '0'
				}
			} else {
				var L, S, startL, startS int
				if a >= b {
					L, S = a, b
					startL, startS = 0, a
				} else {
					L, S = b, a
					startL, startS = a, 0
				}

				hashL := getHashS(startL, startL+L)
				hashSStr := getHashS(startS, startS+S)

				j := 0
				possible := true
				for j < m {
					if j+L <= m && getHashT(j, j+L) == hashL {
						j += L
					} else if j+S <= m && getHashT(j, j+S) == hashSStr {
						j += S
					} else {
						possible = false
						break
					}
				}
				if possible {
					ans[i-1] = '1'
				} else {
					ans[i-1] = '0'
				}
			}
		}
		out.WriteString(string(ans) + "\n")
	}
}

func main() {
	solve()
}