#2556 요리조리 Palindrome

1 s   64 MB  

Description

Palindrome이란 오른쪽에서 왼쪽으로 읽었을 때와 왼쪽에서 오른쪽으로 읽었을 때가 서로 같 은 1개 이상의 문자로 이루어진 문자열을 말한다. 예를 들어 “madam”, “z”, “noon” 등의 문자열 이 palindrome이다. 각 셀마다 하나의 알파벳이 입력되어 있는, 가로와 세로 길이가 각각 K인 2차원 K*K 테이블이 있다. 이 테이블을 아래에서 설명하는 것처럼 4가지 다른 순서로 읽었을 때, 4개가 모두 같은 문 자열이 된다면 이를 “요리조리 Palindrome”이라고 한다. 아래의 예제는 K=3일 때 각 셀의 좌표를 나타내며, (a, b)에서 첫 번째 좌표 a는 행을, 두 번째 좌표 b는 열을 의미한다. -(1, 1)의 셀부터, 각 행이 끝날 때까지 오른쪽으로 읽고 아래 행을 같은 방법으로 읽는다. 테이블 1: abcdefghi 테이블 2: -(1, 1)의 셀부터, 각 열이 끝날 때까지 아래쪽으로 읽고 오른쪽열을 같은 방법으로 읽는다.

- (1, 1)의 셀부터, 각 행이 끝날 때까지 오른쪽으로 읽고 아래 행을 같은 방법으로 읽는다. 테이블 1: abcdefghi 테이블 2: tableabellbekebllebaelbat - (1, 1)의 셀부터, 각 열이 끝날 때까지 아래쪽으로 읽고 오른쪽 열을 같은 방법으로 읽는 다. 테이블 1: adgbehcfi 테이블 2: tableabellbekebllebaelbat - (K, K)의 셀부터, 각 행의 시작부분까지 왼쪽으로 읽고 위 행을 같은 방법으로 읽는다. 테이블 1: ihgfedcba 테이블 2: tableabellbekebllebaelbat - (K, K)의 셀부터, 각 열의 시작부분까지 위쪽으로 읽고 왼쪽 열을 같은 방법으로 읽는다. 테이블 1: ifchebgda 테이블 2: tableabellbekebllebaelbat

Input

입력의첫줄에는 테스트케이스의 개수 T(1<=T<=99 )가 주어진다. 각 케이스는 K+1 줄 로 구성되어있다. 각케이스의첫줄에는 테이블의 크기인 K ( 1 <= K <= 100 ) 값이 주어지고 다 음 K줄은 테이블의 셀의 정보가 주어진다. 각 줄마다 한 행씩 차례로 입력된다. 각 행은 K 길이 의 문자열이며, 한 셀에는 한 개의 알파벳 소문자만 들어갈 수 있다.

Output

주어진 테이블이 ‘요리조리 Palindrome’이면 “YES”를 출력하고, 아니면 “NO”를 출력한다.

Sample Input

Sample Output

2
3
abc
def
ghi
5
table
abell
bekeb
lleba
elbat
NO
YES

Source

2007 Soongsil University Campus Programming Contest, test data : Kogle