1452 -- String Statistics
Time Limit :1000 MS Memory Limit :65536 KB
Accepts : 28 Submits : 62
User Accepts : 19 User Submits : 19
<Submit>   <Statistics>   <Discuss>

Description

You have an n × n matrix of lower-case letters. You start from somewhere in the matrix, walk in one of the eight directions (left, right, up, down, up-left, up-right, down-left, down-right) and concatenate every letter you meet, in the order you see them, to form a string. You can stop anywhere (possibly not moving at all!), but you cannot go out of the matrix, or change direction in the middle of the journey. How many different strings can you get?

Input

The first line contains t (1 t 10), the number of test cases followed. Each test case begins with one integer n(1 n 50), followed by n lines, containing the matrix. The matrix will contain lower-case letters only.

Output

For each test case, print the number of different strings you can get.

Sample Input

2 
2
aa
bb
3
aba
bcc
daa

Sample Output

6 
31

 

Source

Zhuhai City Contest 2008
<Submit>   <Statistics>   <Discuss>
 


Powered by Zhang Zhaoning PDL College of Computer
Since 2006.03.09 | 2007.11.22 | 2010.03.02 Copyright (r) 2006 - 2010 All Rights Reserved