I-好想成为人类啊_2025年华为杯广东工业大学程序设计竞赛（同步赛）

好想成为人类啊

比赛主页

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

丰川祥子一直在寻找成为人类的方法。上了大学之后，她加入了本校的 ACM 集训队，并开始打 Codeforces。

一天，她正如往常一样打算参加 Codeforces 线上比赛时，却不料点进去看到的是 Cloudflare 的验证码。这个验证码的要求居然是这样的：

我们定义 $S[l;r]$ 是 $S$ 的一个连续的子串 $S_{l}S_{l+1}\cdots S_{r}$ ( $1\le l \le r \le |S|$ )
若字符串 $S$ 的某段子串 $S[l;r] = T$ ，那么我们就说 $[l,r]$ 是字符串 $T$ 的一个出现区间。
给定字符串 $S$ 和字符串 $T$ ，你需要选取一个标记集合 $a = \{a_1,a_2,...,a_k\}$ ，使得对于每个出现区间 $[l, r]$ ，都存在一个 $a_i$ $(1 \leq i \leq k)$ ，满足 $l \leq a_i \leq r$ 。

例如，当 $\textstyle S = \texttt{ababa}$ 且 $\textstyle T = \texttt{aba}$ 时，出现区间为 $[1,3]$ 和 $[3,5]$ ，而祥子只需要标记集合 $\{3\}$ 即可覆盖两个区间，也可以选择标记集合 $\{1,5\}$ ，这样也可以覆盖两个区间，她甚至可以选择标记集合 $\{1,2,3,4,5\}$ ，但是这样就得点 $5$ 下，很麻烦。

擅长键盘的 Saki 酱很快就敲出了 “在一个字符串找另一个字符串的所有出现位置” 的代码，但她希望以尽量少的标记次数来完成本次验证，尽快成为人类！

塑料看完这一集之后立刻把这个问题丢给了你。你的任务就是输出最小的满足条件的标记集合的大小。

输入描述:

输入包含多组测试数据。

第一行包括一个正整数 $T$ $(1 \leq T \leq 10^4)$ ，表示数据组数；

接下来对于每组测试数据：

第一行输入两个正整数 $n$ 和 $m$ $(1 \leq n,m \le 10^3)$ ，表示字符串 $S$ 和 $T$ 的长度；

接下来一行输入一个长度为 $n$ 的字符串 $S$ ;

接下来一行输入一个长度为 $m$ 的字符串 $T$ 。

保证所有字符串都由英文小写字母构成。

保证每个测试点所有测试数据的 $n$ 之和与 $m$ 之和均不超过 $2^{14}$ 。

输出描述:

对于每组测试数据，输出一行一个非负整数 $x$ ，表示最小的满足条件的标记集合的大小。

示例1

输入

复制

2
5 3
ababa
aba
20 4
sakisakisakisakisaki
miku

输出

复制

1
0