1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define maxn 1050000
19 char s[maxn];
20 int slen, len;
21 int next[maxn];
22 int getnext() {
23     int i = 1, j = 0, cnt = 0;
24     next[1] = 0;
25     while(i <= len) {
26         if(j == 0 || s[i] == s[j]) {
27             i++, j++, next[i] = j;
28             if(next[i] == slen + 1) cnt++;
29         } else j = next[j];
30     }
31     return cnt;
32 }
33 
34 int main() {
35     int T;
36     scanf("%d", &T);
37     while(T--) {
38         scanf("%s", s + 1);
39         slen = strlen(s + 1);
40         s[slen+1] = '$';
41         scanf("%s", s + slen + 2);
42         len = strlen(s + 1);
43         printf("%d\n", getnext());
44     }
45     return 0;
46 }
47