Str

对于一个字符串 $s$，定义 $rev(s)$ 为它的反串，$abc$ 的反串为 $cba$。
有 $n$ 个串，第 $i$ 个串为 $s[i]$。

1. 先决定一个整数 $k~(1\leq k \leq n)$ (这一步有 $n$ 种方案)
2. 有序地从 $n$ 个串中，选出 $k$ 个串，设第 $i$ 个选择的串为 $t[i]$（这一步有 $A_{n}^{k}$ 种方案）
3. 对于每个串我们可以决定是否翻转它，如果翻转第 $i$ 个串，那么 $t[i]=rev(t[i])$。（这一步有 $2^k$ 种方案）

求有多少种方案使得 $str = t[1]+t[2]+...+t[k]$ ($+$ 表示字符串拼接) 是回文串。

第一行输入一个整数 $T$，代表 $T~(1 \leq T \leq 20)$ 组数据。
对于每组数据，第一行一个数字 $n~(1\leq n \leq 10)$，表示串的个数，接下来 $n$ 行，第 $i$ 行表示字符串 $s[i]$。
输入保证，$n \geq 5$ 的数据不超过 5 组，每组数据字符串长度之和不会超过 1000。

输出 $T$ 行，每行一个整数表示答案。

2
2
a
a
2
a
ab

12
6

样例描述
样例1有 s1,rev(s1),s2,rev(s2),s1+s2,s1+rev(s2),rev(s1)+s2,rev(s1)+rev(s2),s2+s1,s2+rev(s1),
rev(s2)+s1,rev(s2)+rev(s1) 一共 12 种。

样例2有 s1,rev(s1),s2+s1,s2+rev(s1),s1+rev(s2),rev(s1)+rev(s2) 共 6 种。

2019 年百度之星·程序设计大赛 - 初赛一