SP9118 GCPC11B - Genetic Fraud

在计算机科学领域，优秀的程序员如同明星一般稀缺和受欢迎。几乎每一天，你都会被卷入一场诉讼中，而这些诉讼都是关于你孩子抚养费的索赔。不过，幸运的是你对基因序列颇有研究。你知道，人类的 DNA 序列可以表示为一个仅包含 'a' 到 'z' 的字符串，长度为 $N$。通过 DNA 序列的相似性测试，可以证明那些对你不利的指控是错误的。 问题在于这些测试并不仅仅针对你。由于实验室忙碌，测试至少需要一年的时间。不过，还有希望。你了解到一些 DNA 实验室的内幕，得知他们如何计算两个 DNA 字符串之间的遗传关系。如果你能协助实验室快速检测两个 DNA 字符串间的遗传关系，你就会获得对你有利的证据。 遗传关系测试（GRT）要求对 DNA 字符串进行大量计算。实验室首先要找出两个 DNA 字符串中所有的相似区域。对于 DNA 字符串 $a$ 和 $b$，如果 $a[i..i+l]$ 和 $b[j..j+l]$ 两个区域的字符之间的差值不超过 1（即对于所有 $0 \le k < l$ 都满足 $|a[i+k] - b[j+k]| \le 1$），那它们即为相似区域。当两个 DNA 序列至少存在一个相似区域达到其长度一半时，GRT 结果被判定为阳性。

第一行输入一个整数 $C$ ($0 < C \le 100$)，表示测试用例的数量。之后的每个测试用例，第一行输入一个整数 $N$ ($1 \le N \le 10^5$)，代表两个待检测 DNA 字符串的长度。接下来的两行，各输入一个由小写字母组成的长度为 $N$ 的字符串，代表需要测试的两个人的 DNA 序列。

对于每个测试用例，输出一行。如果 GRT 测试结果为阳性，输出 `POSITIVE`；如果测试结果为阴性，输出 `NEGATIVE`。 **本翻译由 AI 自动生成**