#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
class Node
{
public:
map<char,Node*> children;
bool islast;
Node* fail;
int id;
Node(int i)
{
islast = false;
fail = NULL;
id = i;
}
};
class trie
{
public:
Node* root;
bool exist[1005];
vector<char> alpha;
bool vis[256];
trie(vector<string> p)
{
root = new Node(-1);
memset(exist,false,sizeof(exist));
memset(vis,false,sizeof(vis));
insert_patterns(p);
automaton();
}
bool contains(map<char,Node*> m, char c)
{
return m.find(c) != m.end();
}
void insert(string s, int id)
{
Node* c = root;
for(int i=0;i<s.size();i++)
{
if(!vis[s[i]])
{
vis[s[i]] = true;
alpha.push_back(s[i]);
}
if(contains(c->children,s[i]))
{
c = c->children[s[i]];
}
else
{
c->children[s[i]] = new Node(id);
c = c->children[s[i]];
}
}
c->islast = true;
}
void insert_patterns(vector<string> p)
{
for(int i=0;i<p.size();i++)
insert(p[i],i);
}
void automaton()
{
queue<Node*> q;
for(int i=0;i<alpha.size();i++)
{
if(!contains(root->children,alpha[i]))
{
root->children[alpha[i]] = root;
}
else
{
q.push(root->children[alpha[i]]);
root->children[alpha[i]]->fail = root;
}
}
while(q.size())
{
Node* p = q.front();
q.pop();
map<char,Node*>::iterator it = p->children.begin();
for(;it!=p->children.end();it++)
{
char ch = it->first;
Node* u = it->second;
q.push(u);
Node* v = p->fail;
while(!contains(v->children,ch))
{
v = v->fail;
}
u->fail = v->children[ch];
}
}
}
void search(string s)
{
Node* cur = root;
for(int i=0;i<s.size();i++)
{
if(!vis[s[i]])
{
vis[s[i]]= true;
alpha.push_back(s[i]);
root->children[s[i]] = root;
}
while(!contains(cur->children,s[i]))
{
cur = cur->fail;
}
cur = cur->children[s[i]];
if(cur->islast)
{
Node* tem = cur;
while(tem!= root)
{
if(tem->islast)
{
exist[tem->id] = true;
}
tem = tem->fail;
}
}
}
}
};
int main()
{
int n;
cin >> n;
while(n--)
{
string s;
cin >> s;
int q;
cin >> q;
vector<string> p;
map<string,int> vis;
int id = 0;
while(q--)
{
string ss;
cin >> ss;
if(vis.find(ss) == vis.end())
{
vis[ss] = id;
}
id++;
p.push_back(ss);
}
trie* t = new trie(p);
t->search(s);
for(int i=0;i<p.size();i++)
{
string r = t->exist[vis[p[i]]] ? "y" : "n";
cout << r << endl;
}
}
system("pause");
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxjc3RyaW5nPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNsYXNzIE5vZGUKewpwdWJsaWM6CgltYXA8Y2hhcixOb2RlKj4gY2hpbGRyZW47Cglib29sIGlzbGFzdDsKCU5vZGUqIGZhaWw7CglpbnQgaWQ7CgoJTm9kZShpbnQgaSkKCXsKCQlpc2xhc3QgPSBmYWxzZTsKCQlmYWlsID0gTlVMTDsKCQlpZCA9IGk7Cgl9Cgp9OwoKY2xhc3MgdHJpZQp7CnB1YmxpYzoKCU5vZGUqIHJvb3Q7Cglib29sIGV4aXN0WzEwMDVdOwoJdmVjdG9yPGNoYXI+IGFscGhhOwoJYm9vbCB2aXNbMjU2XTsKCgl0cmllKHZlY3RvcjxzdHJpbmc+IHApCgl7CgkJcm9vdCA9IG5ldyBOb2RlKC0xKTsKCQltZW1zZXQoZXhpc3QsZmFsc2Usc2l6ZW9mKGV4aXN0KSk7CgkJbWVtc2V0KHZpcyxmYWxzZSxzaXplb2YodmlzKSk7CgkJaW5zZXJ0X3BhdHRlcm5zKHApOwoJCWF1dG9tYXRvbigpOwoJfQoKCWJvb2wgY29udGFpbnMobWFwPGNoYXIsTm9kZSo+IG0sIGNoYXIgYykKCXsKCQlyZXR1cm4gbS5maW5kKGMpICE9IG0uZW5kKCk7Cgl9CgoJdm9pZCBpbnNlcnQoc3RyaW5nIHMsIGludCBpZCkKCXsKCQlOb2RlKiBjID0gcm9vdDsKCgkJZm9yKGludCBpPTA7aTxzLnNpemUoKTtpKyspCgkJewoJCQlpZighdmlzW3NbaV1dKQoJCQl7CgkJCQl2aXNbc1tpXV0gPSB0cnVlOwoJCQkJYWxwaGEucHVzaF9iYWNrKHNbaV0pOwoJCQl9CgoJCQlpZihjb250YWlucyhjLT5jaGlsZHJlbixzW2ldKSkKCQkJewoJCQkJYyA9IGMtPmNoaWxkcmVuW3NbaV1dOwoJCQl9CgkJCWVsc2UKCQkJewoJCQkJYy0+Y2hpbGRyZW5bc1tpXV0gPSBuZXcgTm9kZShpZCk7CgkJCQljID0gYy0+Y2hpbGRyZW5bc1tpXV07CgkJCX0KCQl9CgoJCWMtPmlzbGFzdCA9IHRydWU7Cgl9CgoJdm9pZCBpbnNlcnRfcGF0dGVybnModmVjdG9yPHN0cmluZz4gcCkKCXsKCQlmb3IoaW50IGk9MDtpPHAuc2l6ZSgpO2krKykKCQkJaW5zZXJ0KHBbaV0saSk7Cgl9CgoJdm9pZCBhdXRvbWF0b24oKQoJewoKCQlxdWV1ZTxOb2RlKj4gcTsKCgkJZm9yKGludCBpPTA7aTxhbHBoYS5zaXplKCk7aSsrKQoJCXsKCgkJCWlmKCFjb250YWlucyhyb290LT5jaGlsZHJlbixhbHBoYVtpXSkpCgkJCXsKCQkJCXJvb3QtPmNoaWxkcmVuW2FscGhhW2ldXSA9IHJvb3Q7CgkJCX0KCQkJZWxzZQoJCQl7CgkJCQlxLnB1c2gocm9vdC0+Y2hpbGRyZW5bYWxwaGFbaV1dKTsKCQkJCXJvb3QtPmNoaWxkcmVuW2FscGhhW2ldXS0+ZmFpbCA9IHJvb3Q7CgkJCX0KCQl9CgoJCXdoaWxlKHEuc2l6ZSgpKQoJCXsKCQkJTm9kZSogcCA9IHEuZnJvbnQoKTsKCQkJcS5wb3AoKTsKCgkJCW1hcDxjaGFyLE5vZGUqPjo6aXRlcmF0b3IgaXQgPSBwLT5jaGlsZHJlbi5iZWdpbigpOwoJCQlmb3IoO2l0IT1wLT5jaGlsZHJlbi5lbmQoKTtpdCsrKQoJCQl7CgkJCQljaGFyIGNoID0gaXQtPmZpcnN0OwoJCQkJTm9kZSogdSA9IGl0LT5zZWNvbmQ7CgoJCQkJcS5wdXNoKHUpOwoKCQkJCU5vZGUqIHYgPSBwLT5mYWlsOwoJCQkJd2hpbGUoIWNvbnRhaW5zKHYtPmNoaWxkcmVuLGNoKSkKCQkJCXsKCQkJCQl2ID0gdi0+ZmFpbDsKCQkJCX0KCgkJCQl1LT5mYWlsID0gdi0+Y2hpbGRyZW5bY2hdOwoKCQkJfQoKCQl9CgoJfQoKCXZvaWQgc2VhcmNoKHN0cmluZyBzKQoJewoJCU5vZGUqIGN1ciA9IHJvb3Q7CgoJCWZvcihpbnQgaT0wO2k8cy5zaXplKCk7aSsrKQoJCXsKCgkJCWlmKCF2aXNbc1tpXV0pCgkJCXsKCQkJCXZpc1tzW2ldXT0gdHJ1ZTsKCQkJCWFscGhhLnB1c2hfYmFjayhzW2ldKTsKCQkJCXJvb3QtPmNoaWxkcmVuW3NbaV1dID0gcm9vdDsKCQkJfQoKCQkJd2hpbGUoIWNvbnRhaW5zKGN1ci0+Y2hpbGRyZW4sc1tpXSkpCgkJCXsKCQkJCWN1ciA9IGN1ci0+ZmFpbDsKCQkJfQoKCQkJY3VyID0gY3VyLT5jaGlsZHJlbltzW2ldXTsKCgkJCWlmKGN1ci0+aXNsYXN0KQoJCQl7CgkJCQlOb2RlKiB0ZW0gPSBjdXI7CgkJCQl3aGlsZSh0ZW0hPSByb290KQoJCQkJewoJCQkJCWlmKHRlbS0+aXNsYXN0KQoJCQkJCXsKCQkJCQkJZXhpc3RbdGVtLT5pZF0gPSB0cnVlOwoKCQkJCQl9CgoJCQkJCXRlbSA9IHRlbS0+ZmFpbDsKCgkJCQl9CgkJCX0KCgkJfQoJfQoKfTsKCmludCBtYWluKCkKewoKCWludCBuOwoJY2luID4+IG47CgoJd2hpbGUobi0tKQoJewoJCXN0cmluZyBzOwoJCWNpbiA+PiBzOwoKCQlpbnQgcTsKCQljaW4gPj4gcTsKCQl2ZWN0b3I8c3RyaW5nPiBwOwoKCQltYXA8c3RyaW5nLGludD4gdmlzOwoKCQlpbnQgaWQgPSAwOwoJCXdoaWxlKHEtLSkKCQl7CgkJCXN0cmluZyBzczsKCQkJY2luID4+IHNzOwoKCQkJaWYodmlzLmZpbmQoc3MpID09IHZpcy5lbmQoKSkKCQkJewoJCQkJdmlzW3NzXSA9IGlkOwoJCQl9CgoJCQlpZCsrOwoJCQlwLnB1c2hfYmFjayhzcyk7CgkJfQoKCQl0cmllKiB0ID0gbmV3IHRyaWUocCk7CgoJCXQtPnNlYXJjaChzKTsKCgkJZm9yKGludCBpPTA7aTxwLnNpemUoKTtpKyspCgkJewoJCQlzdHJpbmcgciA9IHQtPmV4aXN0W3Zpc1twW2ldXV0gPyAieSIgOiAibiI7CgkJCWNvdXQgPDwgciA8PCBlbmRsOwoJCX0KCgl9CgoJc3lzdGVtKCJwYXVzZSIpOwoKCn0K