Submit | All submissions | Best solutions | Back to list |

## 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).

### 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

1 5 ab a a ab a a baaaa a a baSample input:12Sample output:

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) |