给定3个只有小写字母的字符串，您必须计算通过组合前两个字符串的两个子序列来构造第三个字符串的方法的数量。

从字符串中删除0个或更多字符后，我们可以获得其子序列。例如“a”、“b”、“c”、“ab”、“ac”、“bc”和“abc”，所有字符串都是“abc”的子序列。子序列也可以是空的。

现在假设有两个子序列“abc”和“de”。通过组合它们，您可以得到以下字符串“abcde”、“abdce”、“abdec”、“adbce”、“adbec”、“adebc”、“dabce”、“dabec”、“daebc”和“deabc”。

输入

输入的第一行包含一个整数T（0<T<271），表示测试用例的数量。

每个测试用例包含3个仅包含小写字符的字符串。字符串的长度介于1和60之间。

输出

对于每个测试用例输出一个整数，表示可以通过上述方法从前两个字符串构造第三个字符串的方法的数量。结果可能很大。您应该输出结果%10007。