유전자 사기

컴퓨터 과학자의 삶은 고달프다. 당신 같은 뛰어난 젊은 인재가 워낙 드물다 보니, 훌륭한 프로그래머는 거의 유명한 영화배우 같은 대접을 받는다. 즉 모두가 당신이 힘들게 번 돈을 노린다는 뜻이다. 사태가 너무 심각해져서 당신은 일 년 중 거의 매일 새로운 소송에 직면하는데, 각 소송은 자기 아이가 당신의 아이라고 주장하며 양육비를 요구하는 사람이 제기한 것이다. 다행히 당신은 유전자 서열에 대해 잘 안다. 사람의 DNA 서열은 'a'부터 'z'까지의 문자만으로 이루어진 길이 $1 \le N \le 1000$ 의 문자열로 나타낼 수 있으며, 아이라고 주장되는 DNA 와 당신 자신의 DNA 사이의 유사도 검사로 당신의 결백을 증명할 수 있다.

문제는 이런 일이 당신에게만 일어나는 게 아니라는 점이다. 모든 검사소가 바빠서 검사 한 번에 최소 일 년이 걸린다. 그래도 아직 희망은 있다. 당신은 어느 DNA 검사소로부터 두 DNA 문자열 사이의 유전적 관계 확률을 계산하는 방법을 알아냈다. 두 DNA 문자열의 유전적 관계를 아주 빠르게 검사하도록 검사소들을 도울 수만 있다면, 당신 자신의 소송에 필요한 증거도 얻을 수 있을 것이다.

유전 관계 검사, 즉 GRT 는 DNA 문자열에 대한 무거운 계산을 필요로 한다. 먼저 두 DNA 문자열 안의 모든 유사한 구간을 찾는다. DNA 문자열의 구간(region) 이란 그 문자열의 연속된 부분 구간을 말한다. 길이가 같은 두 구간(각 문자열에서 하나씩)이 유사하다는 것은, 정렬된 모든 위치에서 두 글자가 알파벳 상에서 최대 $1$ 만큼만 차이 난다는 뜻이다. 즉 정렬된 글자 $a_i$, $b_j$ 에 대해 $|a_i - b_j| \le 1$ 이다. (두 구간은 각자의 문자열에서 서로 다른 위치에서 시작해도 된다.) 두 DNA 서열의 GRT 는, 두 서열이 서열 길이의 절반 이상, 즉 $\lceil N/2 \rceil$ 이상의 길이를 갖는 유사한 구간을 가지면 양성이고, 그렇지 않으면 음성이다.

첫 줄에 테스트 케이스의 수 $C$ 가 주어진다 ($0 < C \le 1000$).

각 테스트 케이스는 세 줄로 이루어진다. 첫 줄에는 두 DNA 문자열의 공통 길이 $N$ 이 주어지고, 이어지는 두 줄에는 각각 정확히 $N$ 개의 소문자로 이루어진 문자열, 즉 비교할 두 DNA 문자열이 주어진다.

각 테스트 케이스마다 한 줄을 출력한다. 유전 관계 검사가 양성이면 POSITIVE 를, 그렇지 않으면 NEGATIVE 를 출력한다.