.You are given two strings C and D and you have to find how many times you can form string D from string C. You are only allow ed to delete some characters from string C and change positions of characters .You are not allowed to use same indexed character of C twice in the same string to form string D.

For example :- C = cdc and D=cd. So we can form 2 strings from C same as D. Two strings are different if atleast at one position you use differently indexed character from C.

Input

First line of input will have no. test cases (T) and each test case contain two strings C and D .
Output

Number of time string D can form from C. Output become large so take module with 10^9+7.

Constraints 1<=T<=100

1<= |A| , |B| <=10^6

Strings consist only lowercase letters 'a' to 'z'