回文 (palindrome)

题目描述

小 N 喜欢回文。

小 N 拿到了三个仅由小写字母组成的字符串 $A,B,C$，他想要从这三个串中各选一些字符组成一个回文串。具体地，他会在三个字符串中各选取一个非空子串 $S_A,S_B,S_C$，并将他们顺次拼接成 $T=S_A+S_B+S_C$，如果 $T$ 是回文串，那么认为这一组子串选取方案是合法的。

小 N 想知道所有合法方案的个数。两个方案不同定义为这三个子串中有一个不同（同个字符串的两个子串不同定义为选取的子串对应的下标不同）。

输入格式

在文件 palindrome.in 中读入。 本题有多组测试数据。 输入第一行有一个整数 $T$，表示数据组数。 对于每一组数据，输入共三行，每一行一个仅由小写字母组成的字符串，分别表示 $A,B,C$。

输出格式

在文件 palindrome.out 中输出。 对于每一组数据，输出一个整数表示合法方案数。

样例

样例输入 #1

4
a b c
ab ba ab
ab ab ab
aa aa aa

样例输出 #1

0 6 8 27

数据范围

令 $L$ 为测试数据中所有字符串长度的最大值。

• 对于20%的数据，$1 \le L \le 10$。
• 对于40%的数据，$1 \le L \le 100$。
• 对于60%的数据，$1 \le L \le 200$。
• 对于另外一部分的数据，保证所有字符串中的所有字符都是在字符集中等概率选取的。
• 对于100%的数据，$1 \le L \le 1000$，$1 \le T \le 10$。