회문 경로

인도의 작은 마을 Ragannagar 사람들은 회문에 빠져 있다. 이 마을에는 0부터 N-1까지 번호가 붙은 N개의 교차로(점이라고도 한다)가 있으며, 모든 두 점 사이에 도로가 있다. 도로는 일방통행이다. 점 i와 점 j (i < j)를 잇는 도로는 i에서 j 방향으로만 갈 수 있다. 각 도로에는 'A'부터 'Z'까지의 알파벳 하나가 적혀 있다. 여행자 Rajar는 0번 점에서 N-1번 점까지 가고 싶어 하며, 그중에서도 가장 긴 회문 경로를 지나려 한다.

위 배치에서 가능한 경로는 다음과 같다.

• ACCA
• ABA
• ACB
• BCA
• AD
• BB
• AA
• C

이 중 가장 긴 회문은 ACCA이므로 Rajar는 이 경로를 택한다. 위 배치가 주어졌을 때, Rajar가 어떤 경로를 택해야 할지 정하라.

입력의 첫 줄에는 테스트 케이스의 개수 T (T ≤ 25)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

• 각 테스트 케이스의 첫 줄에는 정수 N (2 ≤ N ≤ 50)이 주어진다.
• 다음 N줄에는 각각 N개의 문자가 주어진다. 각 문자는 'A'부터 'Z'까지의 알파벳이다. i번째 줄의 j번째 문자는 i번 점과 j번 점을 잇는 도로의 라벨이며, j번째 줄의 i번째 문자와 같다. i번째 줄의 i번째 문자는 *이며, 도로가 없음을 뜻한다.

테스트 케이스마다 한 줄을 출력한다. 가장 긴 회문 경로를 출력하고, 그런 경로가 없으면 "NO PALINDROMIC PATH"를 출력한다. 따옴표는 설명을 위한 것이다. 가장 긴 경로가 여러 개면 사전순으로 가장 앞서는 경로를 출력한다.