10069 - Distinct Subsequences

本題要計算一個字串內選擇一組特定子字串的所有組合方式之總數。定義兩個字串X = x1x2...xm, Z = z1z2...zk，如果我們說Z是X的子字串，則可以找到一個嚴格遞增子序列表示X內字元的索引，使得對所有i1...ij...ik(j=1~k)使得xij = zj。例如Z=bcdb為X=abcbdab的子字串，其索引序列為< 2, 3, 5, 7>。

本題給你一個字串X與子字串Z，請你找出所有可能的索引序列總數。

Input

輸入的第一列有一個整數N表示測試資料的總數。每組測試資料的第一列為字串X，為全小寫的字串，其長度不超過10000個字元，第二列為字串Z，為全小寫的字串，其長度不超過100個字元。注意所有子字串的組合不超過10^100個。

Output

請每組測試資料輸出一列表示所有子字串組合的總數。

Sample Input

2
babgbag
bag
rabbbit
rabbit

Sample Output

5
3

____________________________________________________________________________________
原文出處