Kaliya has captured sister of Mr. Natwarlal and kept her in a cell which can be opened only when a particular sequence of squares are pressed in a board having nxn squares with some letters printed over them. Natwarlal somehow managed to get the sequence letters from Kaliya but when he tried to figure out the correct sequence of squares, he found that he has been tricked as the letters over squares were not unique.The letter sequence is just a hint for the actual sequence of the squares to be pressed. There is one more catch in the game.He can only press squares which lies diagonally to the previously pressed square and he can use the previously pressed square again if he needs.

Note : letter can contain any ascii character

For example :

B X A X X
X A X X X
X B B X X
X A X A X
X X B X X

The sequence ABA can be found in 14 different ways – corresponding to the following squares:

A B A
(1,1) (0,0) (1,1)
(1,1) (2,2) (3,1)
(1,1) (2,2) (3,3)
(1,1) (2,2) (1,1)
(3,1) (2,2) (3,1)
(3,1) (2,2) (3,3)
(3,1) (4,2) (3,1)
(3,1) (4,2) (3,3)
(3,1) (2,2) (1,1)
(3,3) (2,2) (3,3)
(3,3) (2,2) (1,1)
(3,3) (2,2) (3,1)
(3,3) (4,2) (3,1)
(3,3) (4,2) (3,3)

Tell Natwarlal the number of possible sequences of the squares

INPUT First line will contain 0<T<60 , the number of test cases followed by 1<=N<=500. Next N lines will contain N space separated letters each. (NxN matrix) Next line will contain sequence of the letters with max length of 500 characters

OUTPUT One line containing the number of possible ways in which squares can be pressed.