eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Генетическое мошенничество

Генетическое мошенничество

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

У компьютерных ученых тяжелая жизнь. Из-за нехватки таких ярких молодых умов, как Вы, хорошие программисты в большинстве своем похожи на знаменитых кинозвезд. Как будто каждый хочет заполучить Ваши кровно заработанные деньги. Ситуация настолько вышла из-под контроля, что с судебными исками приходится сталкиваться почти каждый день. Каждый иск подается кем-то, требующим алиментов на Вашего предполагаемого ребенка. К счастью для Вас, Вы довольно много знаете о генетических последовательностях. Вы знаете, что последовательность ДНК человека может быть представлена строкой длины n, содержащей только символы от 'a' до 'z'. И Вы знаете, что проверка на сходство цепочек ДНК предполагаемого ребенка с Вашими собственными может доказать Вашу невиновность.

Единственная проблема в том, что это происходит не только с Вами. Поскольку все лаборатории заняты, тестирование займет не менее года. Однако не вся надежда потеряна. Вам удалось получить в одной из лабораторий ДНК информацию о том, как вычислить вероятность генетического родства между двумя цепочками ДНК. Если бы Вы только могли помочь лабораториям ДНК очень быстро проверить две цепочки ДНК на генетическое родство, Вы могли бы получить доказательства, необходимые для Ваших собственных судебных исков.

Тест на генетическое родство, или ТГР, требует некоторых трудных вычислений на строках ДНК. Сначала просматриваются все схожие участки в двух цепочках ДНК. Под областью цепочки ДНК мы понимаем последовательный интервал внутри цепочки ДНК. Области a[i .. i + l]~(0 \le i < n - l) и b[j..j+l]~(0 \le j < n - l) цепочек ДНК a, b подобны друг другу, если |a[i+k] - b[j+k]| \le 1 для 0 \le k \le l. ТГР между двумя последовательностями ДНК является положительным, если две последовательности ДНК имеют схожую область, по крайней мере, половину длины последовательностей ДНК.

Вхідні дані

В первой строке задано количество тестов c~(0 < c \le 1000). Первая строка каждого теста содержит целое число n~(1 \le n \le 1000) — длину двух тестируемых цепочек ДНК. Каждая из следующих двух строк содержит строку из n строчных букв. Они задают две подстроки ДНК двух людей, подлежащих тестированию.

Вихідні дані

Для каждого теста выведите одну строку. Если ТГР положителен, то выведите POSITIVE. Выведите NEGATIVE, если тест не пройден.

Приклад

Вхідні дані #1
3
4
aaaa
bbcc
8
iacdefgh
abeaaaaa
8
iacdefgh
abeafaaa
Вихідні дані #1
POSITIVE
NEGATIVE
NEGATIVE
Джерело 2011 ICPC German Collegiate Programming Contest, Задача B