题目描述

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

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

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

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

输入格式

第一行输入组数 \(T\)。

每组数据输入两行表示两个字符串 \(S\) 和 \(T\)，

数据保证： \(n \le 2000\)，\(T \le 10\)。

输出格式

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

样例输入

2
ab
ac
aba
bba

样例输出

2
15