PALSEC - Choosing a Palindromic Sequence

no tags 

Given two sequences of words: X=(x1,...,xn) and Y=(y1,...,yn), determine how many binary sequences P=(p1,...,pn) exist, such that the word concatenation z1z2...zn, where zi=xi iff pi=1 and zi=yi iff pi=0, is a palindrome (a word which is the same when read from left to right and from right to left).

Input

The input begins with the integer t, the number of test cases. Then t test cases follow.

For each test case the first line contains the positive integer n - the number of words in a sequence (1<=n<=30). The following n lines contain consecutive words of the sequence X, one word per line. The next n lines contain consecutive words of the sequence Y, one word per line. Words consist of lower case letters of the alphabet ('a' to 'z'), are non-empty, and not longer than 400 characters.

Output

For each test case output one line containing a single integer - the number of different possible sequences P.

Example

Sample input:
1
5
ab
a
a
ab
a
a
baaaa
a
a
ba

Sample output:
12


Added by:adrian
Date:2004-08-07
Time limit:1.272s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:IV Polish Olympiad in Informatics (Wojciech Rytter)