package Kmp;
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        while(a--!=0) {
            String ss = sc.next();
            String s = sc.next();
            int sum = kmp(ss,s);
            System.out.println(sum);
        }
        sc.close();
    }
    public static int kmp(String ss,String s){
        int[] next = next(s);
        int i = 0,j = 0,cnt = 0;
        int len1 = s.length();
        int len2 = ss.length();
        while(i < len1){
            if(j < len2 && (j == -1 ||s.charAt(i)==ss.charAt(j))){
                i++;
                j++;
            }else{
                j = next[j];
            }
            if(j == len2){
                cnt++;
            }
        }
        return cnt;
    }
    public static int[] next(String ss){
        int[] next = new int[10001];
        int i = 0,j = -1;
        next[0] = -1;
        int len2 = ss.length();
        while(i < len2){
            if(j == -1 || ss.charAt(i) == ss.charAt(j)){
                i++;
                j++;
                next[i] = j;
            }else{
                j = next[j];
            }
        }
        return next;
    }
}