Given two sequences of words: X=(x₁,...,x_n) and Y=(y₁,...,y_n), determine how many binary sequences P=(p₁,...,p_n) exist, such that the word concatenation z₁z₂...z_n, where z_i=x_i iff p_i=1 and z_i=y_i iff p_i=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