// 查找串t在串s中出現(xiàn)的次數(shù)，模式匹配，KMP算法
#include < iostream >
#include < string >
#include < vector >
using namespace std;

string s,t;
vector < int > next;

void nextIt()
... {
int i = 0 ,j =- 1 ,n = t.size();
next[ 0 ] =- 1 ;

while (i < n)
... {
if (j ==- 1 || t[i] == t[j])
... {
i ++ ;
j ++ ;
next[i] = j;
}
else
j = next[j];
}
}

int countIt()
... {
int i = 0 ,j = 0 ,cnt = 0 ,n = s.size(),m = t.size();
while (i < n)
... {
if (j ==- 1 || s[i] == t[j])
... {
i ++ ;
j ++ ;
if (j == m)
... {
cnt ++ ;
j = next[j];
}
}
else
j = next[j];
}
return cnt;
}

void run()
... {
cin >> t >> s;
next.resize(t.size() + 1 );
nextIt();
cout << countIt() << endl;
}

int main()
... {
int n;
cin >> n;
for ( int i = 0 ;i < n;i ++ )run();
return 0 ;
}