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$ 行，每行一个整数表示答案。