题目描述

学期结束了。你知道，第一学期结束后就要放假了。假期里，Noora 决定回到 Vičkopolis。作为送给 Leha 的一份小礼物，她从 Pavlopolis 带回来了一根长度为 $m$ 的香肠。众所周知，任何香肠都可以表示为一个长度等于香肠长度的小写英文字母串。

Leha 非常高兴，立刻把香肠吃掉了。但他很快意识到自己的行为相当不得体——毕竟那是个纪念品！于是这个“黑客”马上赶去肉店。不幸的是，店里只剩下一根长度为 $n$ 的另一根香肠。但 Leha 并没有沮丧，还是把它买了下来。回到家后，他决定把买回来的香肠切成若干段，从左到右依次对这些段进行编号，从 $1$ 开始编号。然后他想选择其中几段，并将它们按它们在原香肠中出现的顺序粘在一起，使得到的新香肠等于 Noora 送给他的那个香肠。但 Leha 只能在粘合时保证左段的编号小于右段的编号。此外，他还知道，如果要粘合超过 $x$ 段，Noora 一定能察觉他作假的纪念香肠，并且非常生气。当然，Leha 并不想让女孩难过。现在，他请你帮忙判断，是否有可能通过切割买来的香肠，并从中粘合出新的香肠，使得 Noora 不会发现任何异常。

形式化地，给定两个字符串 $s$ 和 $t$，其中字符串 $s$ 长度为 $n$，字符串 $t$ 长度为 $m$。你需要从 $s$ 中选择若干不相交的子串，保证将这些子串按其在 $s$ 中原有顺序拼接起来后，恰好得到 $t$。定义 $f(s, t)$ 为所需选择的最小子串个数，如果不可能选择出这样的子串，则 $f(s, t)=\infty$。Leha 很想知道是否有 $f(s, t)\leq x$。

本题多组数据T,(T<=5)

输入格式

第一行为数据组数，接下来对每组数据有五行。

第一行包含一个整数 $n$（$1\leq n\leq 10^{5}$），表示 Leha 买的香肠长度，即字符串 $s$ 的长度。

第二行包含一个长度为 $n$ 的字符串 $s$，仅包括小写英文字母。

第三行包含一个整数 $m$（$1\leq m\leq n$），表示 Noora 送的香肠长度，即字符串 $t$ 的长度。

第四行包含一个长度为 $m$ 的字符串 $t$，仅包括小写英文字母。

第五行包含一个整数 $x$（$1\leq x\leq 30$），表示最多允许粘合的香肠段的数量，超过这个数量 Noora 一定会察觉。

输出格式

输出T行，如果 Leha 能够成功得到新的香肠且不会被 Noora 察觉，输出 "YES"（不含引号），否则输出 "NO"（不含引号）。

输入输出样例 #1

输入 #1

2
9
hloyaygrt
6
loyyrt
3
9
hloyaygrt
6
loyyrt
2

输出 #1

YES
NO

说明/提示

以下举例说明。

以第一个样例为例，Leha 最优的切割方法如下：hloyaygrt = h + loy + a + y + g + rt。然后将这些段编号为 $1$ 到 $6$：

• h —— 编号 $1$

• loy —— 编号 $2$

• a —— 编号 $3$

• y —— 编号 $4$

• g —— 编号 $5$

• rt —— 编号 $6$

在此基础上，Leha 只需要粘合编号为 $2$，$4$ 和 $6$ 的部分即可，得到 loyygrt，与 Noora 送的香肠一致。因此需要粘合 $3$ 段。因为 $x=3$，所以应输出 "YES"。

在第二个样例中，香肠内容相同，但是 $x=2$，因此应输出 "NO"。

数据范围

包含下列分段数据，分值不确定 x = 1 n,m <= 200 n,m <= 2000 n,m<=100000