### 问题描述 在一个神奇而古老的王国中，有两位年轻的冒险家，他们分别是小蓝和小桥。小蓝和小桥是无所不能的搭档，他们一起探索世界，解决难题，为王国带来和平与繁荣。 某一天，他们听说了一个传说中的宝藏，据说宝藏隐藏在一个神秘的迷宫中。为了找到宝藏，他们必须解决类似的 $N$ 道谜题。 小蓝和小桥找到了谜题的描述。谜题的描述由两个字符串组成，分别是 $A$ 和 $B$。 对于每个谜题，他们需要计算，在字符串 $A$ 的所有不同排列中，有多少个排列是字符串 $B$ 的子串。 注意，本题只考虑字符串 $A$ 的不同排列，不考虑相同排列的重复计数。 请你帮助小蓝和小桥解决这些谜题，计算出满足条件的不同排列数量。 ### 输入格式 第一行一个整数 $N$，表示谜题的数量。 接下来 $N - 1$ 行，每两行一组数据，每组数据中： 第一行一个字符串 $A$ 。 第二行一个字符串 $B$。 字符串 $A$ $B$ 都只包含小写字母 a~z。 ### 输出格式 输出 $N$ 行，每行一个整数，表示作为字符串 $B$ 的子串出现的 $A$ 的不同排列的数量。 ### 样例输入 ```text 2 lan anllnananl qiao qiaoqioaoqoi ``` ### 样例输出 ```text 2 4 ``` ### 数据规模 $1 \leq N \leq 10 $。 $1 \leq |A| \leq 20 \leq |B| \leq 10^4$。