Genetic Fraud

Interview

Time limit1sMemory limit128 MB

Summary
Decide whether two equal-length strings share an aligned substring of length at least ceil(N/2) where every pair of aligned letters differs by at most 1.
Level

Medium6 of 10

Topics
String, Two pointers, Sliding window, Binary search
Solved
No attempts yet

Problem

Computer scientists have a rough life. Because bright young minds like yours are in short supply, good programmers are treated almost like famous movie stars — it seems everyone wants to get their hands on your hard-earned cash. Things have gotten so out of hand that you face a new lawsuit nearly every day of the year, each one filed by someone claiming alimony for a child they allege is yours. Luckily, you know a great deal about genetic sequences: a human DNA sequence can be represented as a string of 1≤N≤10001 \le N \le 1000 characters, each from 'a' to 'z', and a similarity test between the alleged child's DNA and your own can prove your innocence.

The only problem is that this does not happen to you alone. All the labs are busy, so a test takes at least a year. Still, not all hope is lost: you managed to get from one of the DNA labs the method for computing the probability of a genetic relationship between two DNA strings. If you could help the labs test two DNA strings for a genetic relationship really fast, you could get the evidence you need for your own lawsuits.

A genetic relationship test, or GRT, requires some heavy computation on the DNA strings. It begins by finding all similar regions within the two DNA strings. A region of a DNA string is a consecutive interval of it. Two regions of equal length (one from each string) are similar whenever, at every aligned position, the two letters differ by at most 11 in the alphabet; that is, ∣ai−bj∣≤1|a_i - b_j| \le 1 for the aligned letters aia_i and bjb_j. (The two regions may begin at different positions in their respective strings.) A GRT between two DNA sequences is positive whenever the two sequences have a similar region of length at least one half the length of the sequences — that is, at least ⌈N/2⌉\lceil N/2 \rceil; otherwise it is negative.

Input

The first line contains the number of test cases CC (0<C≤10000 < C \le 1000).

Each test case consists of three lines: an integer NN, the common length of the two DNA strings, followed by two lines that each contain a string of exactly NN lower-case letters — the two DNA strings to compare.

Output

For each test case, print a single line: POSITIVE if the genetic relationship test is positive, or NEGATIVE if it is not.

Examples1

  1. Example 1

    Input
    3
4
aaaa
bbcc
8
iacdefgh
abeaaaaa
8
iacdefgh
abeafaaa
    Expected output
    POSITIVE
NEGATIVE
NEGATIVE