题目描述

小N喜欢回文。 小N拿到了三个仅由小写字母组成的字符串A,B,C，他想要从这三个串中各选一 些字符组成一个回文串。 具体地，他会在三个字符串中各选取一个非空子串$S_A,S_B,S_C$，并将他们顺次拼接成 T =$S_A+S_B+S_C$，如果T 是回文串，那么我们认为这一组子串选取方案是合法的。 小N想要知道所有合法方案的个数，两个方案不同定义为这三个子串中有一个不同， 同个字符串的两个子串不同定义为选取的子串对应的下标不同。 但他太菜了，算不出来，只能请你帮忙求解了。 答案不会很大，所以你不用对998244353 取模

输入格式

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

输出格式

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

Samples

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

0
6
8
27

样例2

见选手目录下的pali/pali2.in与pali/pali2.out。 更多样例见下发文件。

数据范围

令L为测试数据中所有字符串长度的最大值。 •对于20%的数据，1≤L≤10。 •对于40%的数据，1≤L≤100。 •对于60%的数据，1≤L≤200。 •对于另外10%的数据，保证所有字符串中的所有字符都是在字符集中等概率选取 的。 •对于100%的数据，1≤L≤1000,1≤T≤10