#include <bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
const int N=1005;
int tag[26];
int ch[N][26];
int fail[N];
int tid;
int ins() {
    string s;
    cin >> s;
    int p=0;
    for(auto c: s) {
        c-='a';
        if(!ch[p][c]) ch[p][c]=++tid;
        p=ch[p][c];
    }
    return p;
}
int Q[N*N*2];
int dis[N];
int mark[N];
int cnt[N];
int val[N];
vector<int> g[N];

void dfs(int x)
{
    for(auto v:g[x])
    {
        val[v]+=val[x];
        dfs(v);
    }
}
void solve() {
    string cc;
    cin >> cc;
    for(int i=0;i<=tid;i++)
        fail[i]=0,memset(ch,0,sizeof(ch));
    memset(tag,0,sizeof(tag));
    for(auto c: cc) tag[c-'a']=1;
    tid=0;
    int p[2];
    p[0]=ins();
    p[1]=ins();
    int l=1,r=0;
    FOR(i,0,25) if(tag[i] && ch[0][i]) Q[++r]=ch[0][i];
    while(l<=r) {
        int p=Q[l++];
        FOR(i,0,25) if(tag[i]) {
            if(ch[p][i]) {
                Q[++r]=ch[p][i];
                fail[ch[p][i]]=ch[fail[p]][i];
            } else ch[p][i]=ch[fail[p]][i];
        }
    }
    FOR(i,0,tid)
        g[i].clear(),val[i]=(i==p[0])-(i==p[1]);
    FOR(i,1,tid)
        g[fail[i]].push_back(i);
    dfs(0);
    // FOR(i,0,tid) FOR(j,0,25) if(tag[j]) cerr << i << ' ' << ch[i][j] << '\n';
    // cerr << p[0] << ' ' << p[1] << endl;
    int res=0,flag=0;
    vector<vector<int> >key;
    key.resize(2);
    FOR(_,0,1) {
        FOR(i,0,tid) dis[i]=-1e9,mark[i]=0,cnt[i]=0;
        // memset(mark,0,sizeof(mark));
        // memset(cnt,0,sizeof(cnt));
        l=1,r=0;
        dis[0]=0;
        Q[++r]=0;
        mark[0]=1;
        while(l<=r) {
            int x=Q[l++];
            mark[x]=0;
            ++cnt[x];
            if(cnt[x]>30+5) {
                continue;
            }
            FOR(i,0,25) if(tag[i]) {
                int y=ch[x][i];
                if(dis[x]+(_==0?1:-1)*val[y]>dis[y]) {
                    // cerr << dis[y] << endl;
                    dis[y]=dis[x]+(_==0?1:-1)*val[y];
                    if(!mark[y]) {
                        Q[++r]=y;
                        mark[y]=1;
                    }
                }
            }
        }
        FOR(i,0,tid) if(cnt[i]>30+5) {
            key[_].push_back(i);
        }
        if(key[_].size())
            res++;
    }
    for(int _=0;_<2;_++)
    {
        l=1,r=0;
        for(int i=0;i<=tid;i++)
            cnt[i]=0;
        for(auto x:key[_])
            Q[++r]=x,cnt[x]=1;
        while(l<=r)
        {
            int x=Q[l++];
            for(int i=0;i<26;i++)
                if(tag[i]&&ch[x][i])
                {
                    if(cnt[ch[x][i]])
                        continue;
                    cnt[ch[x][i]]=1;
                    Q[++r]=ch[x][i];
                }
        }
        for(auto x:key[_^1])
            if(cnt[x])
                flag=1;
    }
    cout << (res<2 || !flag) << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}