떠돌이 벼룩 조련사

바이트랜드는 떠돌이 벼룩 조련사로 유명하다. 조련사는 길들인 벼룩에게 춤을 가르친다. 벼룩은 음악의 박자에 맞추어 정확하게 도약한다. 조련사는 탁자 위에 번호가 매겨진 동전들을 한 줄로 놓는데, 이 동전들이 특정한 순서로 놓여 있다고 가정하지는 않는다.

각 동전에는 "i→j" 형태의 문구가 적혀 있다. 여기서 i는 이 동전의 번호이고, j는 이 동전 위에 앉은 벼룩이 도약해야 할 동전의 번호이다. 조련사는 모든 동전 위에 벼룩을 한 마리씩 올려놓고 음악을 켠다. 음악의 매 박자마다 각 벼룩은 자신이 앉아 있는 동전(번호 i)에 적힌 j 번호의 동전으로 곧바로 도약한다. 춤을 추는 동안 여러 벼룩이 같은 동전 위에 모일 수도 있으며, 그럴 경우 이후로는 함께 도약한다.

동전이 n개, 벼룩이 n마리 있다고 하자. 동전 1, 2, …, n에 어떤 번호가 적혀 있는지 정하는 순간 공연은 완전히 결정된다. 그러나 서로 다른 두 동전 집합이라도 적절한 순서로 배열하면 똑같은 공연을 만들어 낼 수 있다. 즉, 한 집합의 동전에 새 번호를 붙여서 다른 집합의 도약과 완전히 일치시킬 수 있다면 두 집합은 같은 종류이다.

예를 들어 동전 세 개에서 도약이 1→2, 2→3, 3→1이면 벼룩들은 원을 그리며 영원히 돌고 결코 한 동전에 모이지 않는다. 반면 1→2, 2→3, 3→3이면 두 박자 뒤에 모든 벼룩이 3번 동전에 모여 이후로는 그곳에서만 뛴다. 이 두 공연은 서로 다르다.

한편 1→2, 2→3, 3→2, 4→4 집합과 1→1, 2→3, 3→2, 4→3 집합은 같은 종류이다. 첫 번째 집합을 왼쪽에서 오른쪽으로, 두 번째 집합을 오른쪽에서 왼쪽으로 늘어놓으면 같은 공연을 볼 수 있기 때문이다.

관객은 같은 공연을 두 번 보는 것을 싫어한다. 따라서 주어진 두 동전 집합에 대해, 동전들을 적절히 배열하여 두 집합이 같은 공연을 만들어 낼 수 있는지 판정하는 프로그램을 작성하라.

첫째 줄에 테스트 케이스의 수 d가 주어진다 (1 ≤ d ≤ 100).

이어지는 각 테스트 케이스는 연속한 세 줄로 이루어진다. 첫 줄에는 동전의 개수 n이 주어진다 (1 ≤ n ≤ 2000). 다음 두 줄은 각각 하나의 동전 집합을 나타내며, 1 이상 n 이하의 정수 n개가 공백 하나로 구분되어 주어진다. i번째 정수는 i번 동전 위에 앉은 벼룩이 도약해야 할 동전의 번호이다.

각 테스트 케이스마다 한 줄에 다음 한 글자만 출력한다.

• T: 두 집합의 동전을 탁자 위에 적절히 배열하여 벼룩들이 똑같이 춤추게 만들 수 있는 경우
• N: 그렇지 않은 경우