open $in, '<', "shortest-accepted.in"; <$in>;
while(<$in>){
s/\$+/()/g;
1 while 0
|| s/ \w \*+ //x
|| s/ (?<![)*a-z
]) (\w*) \
| (\w*) (?![(a
-z
]) / $capture_1 = $1, $capture_2 = $2,
(
)[0]
/xe
|| s/\( (\w*) \) \*+ //x
|| s/\( (\w*) \) /$1/x ;
}
b3BlbiAkaW4sICc8JywgInNob3J0ZXN0LWFjY2VwdGVkLmluIjsKPCRpbj47CndoaWxlKDwkaW4+KXsKCWNob21wOwoJcy9cJCsvKCkvZzsKCQoJMSB3aGlsZSAwCgl8fCBzLyBcdyBcKisgLy94Cgl8fCBzLyAoPzwhWykqYS16XSkgKFx3KikgXHwgKFx3KikgKD8hWyhhLXpdKSAvIAoJCSRjYXB0dXJlXzEgPSAkMSwgJGNhcHR1cmVfMiA9ICQyLCAKCQkoCgkJc29ydCB7IChsZW5ndGggJGEpIDw9PiAobGVuZ3RoICRiKSB8fCAkYSBjbXAgJGIgfSAoICRjYXB0dXJlXzEsICRjYXB0dXJlXzIgKSAKCQkpWzBdCgkJL3hlCgl8fCBzL1woIChcdyopIFwpIFwqKyAvL3gKCXx8IHMvXCggKFx3KikgXCkgLyQxL3ggOwoJCgkobGVuZ3RoKSBvciAkXyA9IHEoJCk7CglwcmludCAkXywgIlxuIgoJfQ==