import itertools as it,re
I=isinstance
def t(q):
 if I(q,str):yield q;return
 if all(I(i,str)for i in q):yield from q;return
 yield from map(''.join,it.product(*[[j for k in i for j in t(k)]for i in q]))
def p(s):
 q=[];f=0
 while s:
  if(n:=s[0])==')':return s[1:],q
  if'('==n:
   s,v=p(s[1:])
   if f:q[-1]=(q[-1],v);f=0
   else:q+=v
  elif'*'==n:q[-1]=[*q[-1],''];s=s[1:]
  elif'|'==n:f=1;s=s[1:]
  else:
   v=re.findall('^[10ε]+',s)[0];s=s[len(v):];v=[''.join([['',i][i in'10']for i in v])]
   if f:q[-1]=[*q[-1],*v];f=0
   else:q+=v,
 return s,q
f=lambda a,b:all(i in k for i in[*t(p(a)[1])]if len(i)<=max(map(len,k:=[*t(p(b)[1])])))
 
s="""
(0|1)*, (0(1*))*, False
0(0*)1(1*), (0*)(1*), True
((10)|(01)|0)*, (1001)*0, False
0, 1, False
1(1*), (1|ε)*1, True
10((10)*), 1((01)*)0, True
ε*, ε, True
"""
for i in filter(None, s.split('\n')):
	a,b,c = i.split(', ')
	assert f(a,b)==[False, True][c=='True']

aW1wb3J0IGl0ZXJ0b29scyBhcyBpdCxyZQpJPWlzaW5zdGFuY2UKZGVmIHQocSk6CiBpZiBJKHEsc3RyKTp5aWVsZCBxO3JldHVybgogaWYgYWxsKEkoaSxzdHIpZm9yIGkgaW4gcSk6eWllbGQgZnJvbSBxO3JldHVybgogeWllbGQgZnJvbSBtYXAoJycuam9pbixpdC5wcm9kdWN0KCpbW2ogZm9yIGsgaW4gaSBmb3IgaiBpbiB0KGspXWZvciBpIGluIHFdKSkKZGVmIHAocyk6CiBxPVtdO2Y9MAogd2hpbGUgczoKICBpZihuOj1zWzBdKT09JyknOnJldHVybiBzWzE6XSxxCiAgaWYnKCc9PW46CiAgIHMsdj1wKHNbMTpdKQogICBpZiBmOnFbLTFdPShxWy0xXSx2KTtmPTAKICAgZWxzZTpxKz12CiAgZWxpZicqJz09bjpxWy0xXT1bKnFbLTFdLCcnXTtzPXNbMTpdCiAgZWxpZid8Jz09bjpmPTE7cz1zWzE6XQogIGVsc2U6CiAgIHY9cmUuZmluZGFsbCgnXlsxMM61XSsnLHMpWzBdO3M9c1tsZW4odik6XTt2PVsnJy5qb2luKFtbJycsaV1baSBpbicxMCddZm9yIGkgaW4gdl0pXQogICBpZiBmOnFbLTFdPVsqcVstMV0sKnZdO2Y9MAogICBlbHNlOnErPXYsCiByZXR1cm4gcyxxCmY9bGFtYmRhIGEsYjphbGwoaSBpbiBrIGZvciBpIGluWyp0KHAoYSlbMV0pXWlmIGxlbihpKTw9bWF4KG1hcChsZW4sazo9Wyp0KHAoYilbMV0pXSkpKQoKcz0iIiIKKDB8MSkqLCAoMCgxKikpKiwgRmFsc2UKMCgwKikxKDEqKSwgKDAqKSgxKiksIFRydWUKKCgxMCl8KDAxKXwwKSosICgxMDAxKSowLCBGYWxzZQowLCAxLCBGYWxzZQoxKDEqKSwgKDF8zrUpKjEsIFRydWUKMTAoKDEwKSopLCAxKCgwMSkqKTAsIFRydWUKzrUqLCDOtSwgVHJ1ZQoiIiIKZm9yIGkgaW4gZmlsdGVyKE5vbmUsIHMuc3BsaXQoJ1xuJykpOgoJYSxiLGMgPSBpLnNwbGl0KCcsICcpCglhc3NlcnQgZihhLGIpPT1bRmFsc2UsIFRydWVdW2M9PSdUcnVlJ10=