回文串

题目描述

给定两个单词序列：$(x_1,\cdots,x_n)$ 和 $(y_1,\cdots,y_n)$。我们共做 $n$ 次选择，第 $i$ 次从 $x_i$ 或 $y_i$ 中选择一个，并将所有被选择的单词将从左到右依次进行合并形成一个串。可以知道，总共有 $2^n$ 种选择。当然，在不同的选择方式下，最终拼成的串可能相同。 如果一个选择形成的串是回文的，即从左到右和从右到左读都相同，则我们说这种选择是对称的选择。

你的任务是写一个程序：

• 读入数 $n$ 和两个单词序列 $(x_1,\cdots,x_n)$ 和 $(y_1,\cdots,y_n)$
• 从被给的序列中选择单词，计算对称选择的数目

输入

第一行是一个正整数 $T$，表示数据组数。

对于每组数据，第一行是一个正整数 $n$。

下面 $n$ 行描述第一个序列，每一行为一个单词 $x_i$ 。

接下来 $n$ 行描述第二个序列，每一行为一个单词 $y_i$ 。

$T\le 12,1\le n\le 30$ ，单词全部由小写的英文字母组成，对于每组数据，$\sum_{i=1}^{n}(|x_i|+|y_i|)\le 400$。

输出

对于每组数据，输出一行，格式为 Case #number: result，其中 $\mathrm{number}$ 表示这是第 $\mathrm{number}$ 组数据，而 $\mathrm{result}$ 为答案。

输入样例

1
5
ab
a
a
ab
a
a
baaaa
a
a
ba

输出样例

Case #1: 12