#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];
int dis[N];
int mark[N];
int cnt[N];
void solve() {
    string cc;
    cin >> cc;
    memset(tag,0,sizeof(tag));
    for(auto c: cc) tag[c-'a']=1;
    memset(ch,0,sizeof(ch));
    memset(fail,0,sizeof(fail));
    memset(cnt,0,sizeof(cnt));
    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) FOR(j,0,25) if(tag[j]) cerr << i << ' ' << ch[i][j] << '\n';
    // cerr << p[0] << ' ' << p[1] << endl;
    int res=0;
    FOR(_,0,1) {
        memset(dis,-1,sizeof(dis));
        memset(mark,0,sizeof(mark));
        l=1,r=0;
        dis[0]=0;
        Q[++r]=0;
        mark[0]=1;
        while(l<=r) {
            int x=Q[l++];
            ++cnt[x];
            if(cnt[x]>tid+5) {
                // cerr << _ << endl;
                ++res;
                break;
            }
            mark[x]=0;
            FOR(i,0,25) if(tag[i]) {
                int y=ch[x][i];
                if(dis[x]+(y==p[_])-(y==p[_^1])>dis[y]) {
                    // cerr << dis[y] << endl;
                    dis[y]=dis[x]+(y==p[_]);
                    if(!mark[y]) {
                        Q[++r]=y;
                        mark[y]=1;
                    }
                }
            }
        }
    }
    cout << (res<2) << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}