题目描述

小木最近在学回文串，他很快就掌握了如何求出一个字符串内有多少个回文串，但是...如果是在两个字符串内找呢？

现给定两个只包含小写字母的字符串 $S$ 和 $T$，长度均为 $n$，你可以在 $S$ 和 $T$ 中分别选取子串 $S'$ 和 $T'$，并将 $T'$ 拼接在 $S'$ 后面组成新字符串。

问有多少种选法，使得组成的新字符串是个回文串。小木被难住了，来请求你帮助他解决这个问题。

注：回文串是指一个字符串，其正读和反读都一样。例如，"abba" 和 "aba" 都是回文串。而"abc"不是回文串。注意空串不是回文串。

输入格式

第一行输入组数 $T$, 每组数据输入两行表示两个字符串$S$和$T$， 数据保证：$n\leq2000$ ，$T\leq10$。

输出格式

每组输出一行整数，表示多少种选法，使得组成的新字符串是个回文串。

2
ab
ac
aba
bba

2
15