public class three {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        String a=in.nextLine();
        for (int i = 0; i < n; i++) {
            sort(in.nextLine());
        }

    }

    public static void sort(String x){
        String[] s = x.split(" ");
        int a=0;
        int b=0;
        int c=0;
        int index=0;
        int num=Integer.valueOf(s[3]);
        if(s[0].length()+s[1].length()<s[2].length()) System.out.println(0);
        else if(s[0].charAt(0)!=s[2].charAt(0)&&s[1].charAt(0)!=s[2].charAt(0)){
            System.out.println(0);
        }else {
            while (index<num&&c<s[2].length()) {
                int l = sort(s[2], s[0], c, a);
                int r = sort(s[2], s[1], c, b);
                if(l==0&&r==0)break;
                if (l > r) {
                    c += l;
                    a += l;
                } else {
                    c += r;
                    b += r;
                }
                index++;
            }
            if(c==s[2].length()) System.out.println(1);
            else System.out.println(0);
        }
    }

    public static int sort(String x,String y,int x1,int y1){
        int index=0;
        while (y1<y.length()&&x1<x.length()&&y.charAt(y1)==x.charAt(x1)){
            y1++;
            x1++;
            index++;
        }
        return index;
    }
}