Palindromic paths

In Ragannagar, a small town in India, people are obsessed with palindromes. There are N road junctions (also called points) labeled 0 to N-1, and roads exist between every pair of points. Roads are one-way. For the road connecting point i to point j (i < j), the direction of travel is from i to j. Each road is labeled with a letter from 'A' to 'Z'. Rajar, the traveler, wants to travel from point 0 to point N-1. He wants to cover the longest palindromic path.

In the arrangement above, the possible paths are:

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

The largest palindrome among these is ACCA, so Rajar takes this path. Given the above configuration, help him decide which path to take.

The first line of input contains an integer T, the number of test cases (T ≤ 25). Each test case is formatted as follows:

• The first line of each test case contains an integer N (2 ≤ N ≤ 50).
• The next N lines contain N characters each. Each character is a letter from 'A' to 'Z'. The j-th character of the i-th line is the label of the road between i and j, and it equals the i-th character of the j-th line. The i-th character of the i-th line is *, meaning no road exists.

Output one line per test case: the longest palindromic path, or "NO PALINDROMIC PATH" if none exists. The quotes are for clarity only. If more than one longest path exists, output the lexicographically smallest one.