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 onewayed and for the road connecting point i to point j (i < j) the direction to travel is i to j. Each road is labeled with a letter between ‘A’ to ‘Z’ . Rajar ,the traveler, wants to travel from point 0 to point N − 1. However he wants to cover the longest palindromic path. In the above arrangement the possible paths to take are: • ACCA • ABA • ACB • BCA • AD • BB • AA •C The largest palindrome amongst these is ACCA, so Rajar will take this path. Given the above configuration, help him decide which path to take.
2/2 Input The first line of input will contain an integer denoting the number of test cases T ≤ 25. Each test case will be formatted as follows: • The first line of each test case contains an integer denoting 2 ≤ N ≤ 50. • The next N lines contain N characters each. Each character is a letter between ‘A’ to ‘Z’. The jth character in the i-th line denotes the label for the road between i to j and this will be equal to the i-th character in the jth line. The i-th character of the i-th line will be ‘’ denoting no road exists. Output Output one line per case (note that quotes are for clarity only). The longest palindromic path available or ‘NO PALINDROMIC PATH’ if none exists. In case more than one longest path exists output the lexicographically smallest one. Sample Input 2 5 ABAC ACBD BCCB ABCA CDBA 5 AXYZ ABQR XBBT YQBA ZRTA* Sample Output ACCA ABBA