## PALSEC - Choosing a Palindromic Sequence

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: C C++ 4.3.2 CPP CPP14 CPP14-CLANG FORTRAN JAVA NODEJS PERL6 PERL PHP PROLOG PYTHON PYTHON3 RUBY TCL Resource: IV Polish Olympiad in Informatics (Wojciech Rytter)