给定两个字符串序列A,B，求A序列不同位置构成的子序列中和B序列相同的有多少个。
例如A序列为a1b2c3d4c5(序列为abcc,12345是为区分位置而加入的数字)，B序列abc
这A序列不同位置构成的子序列中和B相同的有a1b2c3，a1b2c5两个
子序列
Input
第一行一个数N（N不大于5）表示有N组测试数据
以下每组测试数据有两行 分别是字符串A和B，其中A串的长度不大于100000，B串的长度不多于1000，并且B长度多于100的只有一组数据
以下每组测试数据有两行 分别是字符串A和B，其中A串的长度不大于100000，B串的长度不多于1000，并且B长度多于100的只有一组数据
Output
对应每组数据输出一个整数，由于数字可能会很大，请对10003取余后再输出
Sample Input
3
a
aa
abcbc
abc
abcdefabcdefdefa
a
Sample Output
0
3
3