题目描述

二叉树的前序、中序、后序遍历介绍如下：

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。

在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的， 已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序，你却不能确定其中序遍历序列，本题就是让你求中序遍历可能有多少种。

输入格式

首先输入一个 $T(T ≤ 20)$, 表示数据集数目。 每组数据，第一行表示该树的前序遍历结果，第二行表示该树的后序遍历结果。树上两个字符不会相同。输入的字符集合为{a-z}，长度不超过26。

输出格式

对于每组数据，输出包含一个不超过长整型的整数，表示可能的中序遍历序列的总数。

样例

输入#1

1
abc
cba

输出#1

4