SP160 PALSEC - Choosing a Palindromic Sequence

Given two sequences of words: X=(x $ _{1} $ ,...,x $ _{n} $ ) and Y=(y $ _{1} $ ,...,y $ _{n} $ ), determine how many binary sequences P=(p $ _{1} $ ,...,p $ _{n} $ ) exist, such that the word concatenation z $ _{1} $ z $ _{2} $ ...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).

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

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