17-比赛1 B

Chef's best friend Jerry gives Chef a string A and wants to know the number of string A that can be obtained from another string B. A is made up of unique characters and every character in B can also be found in A. Chef is only allowed to remove string A from string B when it appears as a substring in string B. After one removal, the gap created will be closed and Chef can repeat the process.

Chef wants you to help Jerry to find the answer.

Input

The first line of the input contains T, the number of test cases.

The first line of each test case contains the string A.

The second line of each test case contains the string B.

Note: Please trim trailing whitespaces

Output

For each test case, output a single line consisting of the number of string A that can be obtained from string B as described.

Constraints

1 ≤ T ≤ 20
1 ≤ |A| ≤ 26
A is made up of uppercase alphabet only
A does not have repeated characters
1 ≤ |B| ≤ 3×10⁵
B only contains characters present in A

Example

Input:
2
TIGER
GTIGETIGERRERTIGTTIGERIGERER
HELO
HELHELLOO

Output:
5
0

Explanation

Test case 1: 5 TIGERs can be obtained from code B as follows:
GTIGETIGERRERTIGTTIGERIGERER
GTIGETIGERRERTIGTIGERER
GTIGERERTIGTIGERER
GTIGERERTIGER
GTIGERER
GER

$i$

 1 # include <bits/stdc++.h>
 2 using namespace std;
 3 int main ()
 4 {
 5     int T; cin>>T;
 6     while(T--)
 7     {
 8         int sum = 0;
 9         string a; cin>>a;
10         string b; cin>>b;
11         int lena = a.length();
12         size_t pos = b.find(a,0);
13         cout<<pos<<endl;
14         for(int i = 0;i < b.length();i++)
15         {
16             //substr()函数
17             if(i+1>=lena&&b.substr(i+1-lena,lena)==a){
18                 ++sum;
19                 //erase()函数
20                 b.erase(i+1-lena,lena);
21                 i-=lena;
22             }
23         }
24         cout<<sum<<endl;
25     }
26 
27     return 0;
28 }