最完全的替换

Problem Description

小 E 拿到了长度分别为 $n, m$ 的 01 串，分别记为 $s$ 和 $t$，保证 $m\leq n$。 小 E 每次操作可以：

• 选择 $s$ 的任意一个长度为 $m$ 的子串 $s[i, i+m-1]$，满足 $1\leq i\leq i +m-1\leq n$。
• 将这个子串替换为 它与 $t$ 异或后的结果。
• 即 $\forall j=1,2,\cdots, m$，将 $s[i+j-1]$ 替换为 $s[i+j-1]\oplus t[j]$，其中 $\oplus$ 为异或操作（c++ 中的 ^）。 小 E 想知道，最少多少次操作可以把 $s$ 变为一个全 0 串。 如果小 E 永远无法做到，输出 -1。

Input

本题有多组测试数据。第一行一个正整数 $T$，表示数据组数，接下来输入每组测试数据。 对于每组测试数据：

• 第一行，两个正整数 $n,m$，分别表示 $s$ 与 $t$ 的长度。
• 第二行，长度为 $n$ 的 01 字符串 s。
• 第三行，长度为 $m$ 的 01 字符串 t。

Output

对于每组测试数据，输出一行一个整数，表示最少操作次数。如果无法做到替换为全 0 串，则输出 -1。

Sample Input

1
5 3
10100
110

Sample Output

2

Hint

对于所有测试数据：$1\leq T\leq 50$，$2\leq n\leq 10^5$，$1\leq m\leq 30$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（8）