aho-korasik

//#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:16777216")
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <cstring>
#include <deque>
#include <iomanip>
#include <cstddef>
#include <queue>
#include <set>


using namespace std;

const int inf = 1000000000;

struct nod
{
    int next[100];
    bool leaf;
    int p, link, ch, len, f;
    vector<int> ind;
};

nod t[100000];
int tsize;

void add_string(string s, int k)
{
    int v = 0;
    for (int i = 0; i < s.size(); i++)
    {
        int l = s[i] - 'a';
        if (t[v].next[l] != -1)
            v = t[v].next[l];
        else
        {
            nod n;
            n.leaf = false;
            n.ch = l;
            n.link = -1;
            n.p = v;
            n.len = t[v].len + 1;
            memset(n.next, -1, sizeof(int) * 100);
            t[v].next[l] = tsize;
            v = tsize;
            t[tsize] = n;
            tsize++;

        }
    }

    t[v].leaf = true;
    t[v].ind.push_back(k);
}

int go(int, int);
int get(int);

int go(int v, int ch)
{
    if (t[v].next[ch] != -1)
        return t[v].next[ch];
    if (v == 0)
        return 0;
    t[v].next[ch] = go(get(v), ch);
    return t[v].next[ch];
}

int get(int v)
{
    if (t[v].link != -1)
        return t[v].link;
    if (v == 0 || t[v].p == 0)
    {
        t[v].link = 0;
        return 0;
    }

    t[v].link = go(get(t[v].p), t[v].ch);
    return t[v].link;
}

bool findstring(string s)
{
    int v = 0;
    for (int i = 0; i < s.size(); i++)
    {
        int l = s[i] - 'a';
        if (t[v].next[l] == -1)
            return false;
        v = t[v].next[l];
    }
    return true;
}

vector<int> a;
vector<char> ans;

void finds(string s)
{
    int v = 0;
    for (int i = 0; i < s.size(); i++)
    {

        for (int v0 = v; v0 != 0; v0 = t[v0].f)
        {
            if (t[v0].leaf)
            {
                for (int r = 0; r < t[v0].ind.size(); r++)
                    ans[t[v0].ind[r]] = 'y';
            }
        }

        v = go(v, s[i] - 'a');
    }

    for (int v0 = v; v0 != 0; v0 = t[v0].f)
    {
        if (t[v0].leaf)
            for (int r = 0; r < t[v0].ind.size(); r++)
                ans[t[v0].ind[r]] = 'y';
    }

        /*bool f = 0;
        for (int j = i; j < s.size(); j++)
        {
            int l = s[j] - 'a';
            if (t[v].next[l] != -1)
                v = t[v].next[l];
            else
            {
                f = 1;
                break;
            }
        }
        if (f && !t[v].leaf)
            continue;
        int k = v;
        while (k != 0)
        {
            if (t[k].leaf)
            {
                ans[t[v].ind] = 'y';
                break;
            }
            k = t[v].f;
        }
        if (k != -1)
            ans[t[v].ind] = 'y';
    }
    return;*/
}

bool mycmp(const int &x, const int &y)
{
    return t[x].len < t[y].len;
}

int main()
{
    ios_base::sync_with_stdio(0);
    //freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);

    int tt;
    cin >> tt;
    string st, s;
    while (tt--)
    {
        a.clear();
        nod n;
        n.ch = -1;
        n.leaf = false;
        n.link = 0;
        n.f = 0;
        n.p = -1;
        n.len = 0;
        memset(n.next, -1, sizeof(int) * 100);
        t[0] = n;
        tsize = 1;
        cin >> st;
        int k;
        cin >> k;
        ans.resize(k);
        for (int i = 0; i < k; i++)
        {
            cin >> s;
            add_string(s, i);
        }

        for (int i = 0; i < tsize; i++)
            a.push_back(i);

        sort(a.begin(), a.end(), mycmp);

        t[0].link = 0;
        t[0].f = 0;
        for (int i = 1; i < a.size(); i++)
        {
            int v = a[i];
            int g = get(v);
            int link = t[v].link;
            if (t[link].leaf)
                t[v].f = link;
            else
                t[v].f = t[link].f;
        }

        ans.assign(k, 'n');
        finds(st);
        for (int i = 0; i < k; i++)
            cout << ans[i] << endl;
    }

    return 0;
}