#include <iostream>
using namespace std;
void czy_parzysta(int &liczba1, bool &suma);
void dodawanie(bool &suma, int &liczba1);
void mnozenie(int &liczba1, int &liczba2);
void mnozenie(bool &suma, int &liczba1);
int main()
{
char znak1,znak2;
int liczba1,liczba2,ile_testow;
cin >> ile_testow;
for(int i=0; i<ile_testow; i++)
{
bool suma=0;
cin >> liczba1;
czy_parzysta(liczba1,suma);
cin >> znak1 >> liczba1 >> znak2 >> liczba2;
do
{
if(znak1!='*' && znak2!='*')
{
dodawanie(suma,liczba1);
liczba1=liczba2;
znak1=znak2;
cin >> znak2;
if(znak2!='=')
cin >> liczba2;
}
else if(znak2=='*')
{
mnozenie(liczba1,liczba2);
cin >> znak2 >> liczba2;
}
else if (znak1=='*')
{
mnozenie(suma,liczba1);
liczba1=liczba2;
znak1=znak2;
cin >> znak2;
if(znak2!='=')
cin >> liczba2;
}
}
while(znak2!='=');
if(znak1=='*')
{
if(suma==1 && liczba1%2==1)
suma=1;
else
suma=0;
}
else
dodawanie(suma,liczba1);
if(suma)
cout << "NIE" << endl;
else
cout << "TAK" << endl;
}
return 0;
}
void czy_parzysta(int &liczba1, bool &suma)
{
if(liczba1%2==0)
suma=0;
else
suma=1;
}
void dodawanie(bool &suma, int &liczba1)
{
if((suma==0 && liczba1%2==0)||(suma==1 && liczba1%2==1))
suma=0;
else
suma=1;
}
void mnozenie(int &liczba1, int &liczba2)
{
if(liczba1%2==1 && liczba2%2==1)
liczba1=1;
else
liczba1=0;
}
void mnozenie(bool &suma, int &liczba1)
{
if(suma%2==1 && liczba1%2==1)
suma=1;
else
suma=0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZvaWQgY3p5X3Bhcnp5c3RhKGludCAmbGljemJhMSwgYm9vbCAmc3VtYSk7CnZvaWQgZG9kYXdhbmllKGJvb2wgJnN1bWEsIGludCAmbGljemJhMSk7CnZvaWQgbW5vemVuaWUoaW50ICZsaWN6YmExLCBpbnQgJmxpY3piYTIpOwp2b2lkIG1ub3plbmllKGJvb2wgJnN1bWEsIGludCAmbGljemJhMSk7CgppbnQgbWFpbigpCnsKICAgIGNoYXIgem5hazEsem5hazI7CiAgICBpbnQgbGljemJhMSxsaWN6YmEyLGlsZV90ZXN0b3c7CiAgICBjaW4gPj4gaWxlX3Rlc3RvdzsKCiAgICBmb3IoaW50IGk9MDsgaTxpbGVfdGVzdG93OyBpKyspCiAgICB7CiAgICAgICAgYm9vbCBzdW1hPTA7CiAgICAgICAgY2luID4+IGxpY3piYTE7CiAgICAgICAgY3p5X3Bhcnp5c3RhKGxpY3piYTEsc3VtYSk7CiAgICAgICAgY2luID4+IHpuYWsxID4+IGxpY3piYTEgPj4gem5hazIgPj4gbGljemJhMjsKCiAgICAgICAgZG8KICAgICAgICB7CiAgICAgICAgICAgIGlmKHpuYWsxIT0nKicgJiYgem5hazIhPScqJykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgZG9kYXdhbmllKHN1bWEsbGljemJhMSk7CiAgICAgICAgICAgICAgICBsaWN6YmExPWxpY3piYTI7CiAgICAgICAgICAgICAgICB6bmFrMT16bmFrMjsKICAgICAgICAgICAgICAgIGNpbiA+PiB6bmFrMjsKICAgICAgICAgICAgICAgIGlmKHpuYWsyIT0nPScpCiAgICAgICAgICAgICAgICAgICAgY2luID4+IGxpY3piYTI7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSBpZih6bmFrMj09JyonKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBtbm96ZW5pZShsaWN6YmExLGxpY3piYTIpOwogICAgICAgICAgICAgICAgY2luID4+IHpuYWsyID4+IGxpY3piYTI7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSBpZiAoem5hazE9PScqJykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbW5vemVuaWUoc3VtYSxsaWN6YmExKTsKICAgICAgICAgICAgICAgIGxpY3piYTE9bGljemJhMjsKICAgICAgICAgICAgICAgIHpuYWsxPXpuYWsyOwogICAgICAgICAgICAgICAgY2luID4+IHpuYWsyOwogICAgICAgICAgICAgICAgaWYoem5hazIhPSc9JykKICAgICAgICAgICAgICAgICAgICBjaW4gPj4gbGljemJhMjsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICB3aGlsZSh6bmFrMiE9Jz0nKTsKCiAgICAgICAgaWYoem5hazE9PScqJykKICAgICAgICB7CiAgICAgICAgICAgIGlmKHN1bWE9PTEgJiYgbGljemJhMSUyPT0xKQogICAgICAgICAgICAgICAgc3VtYT0xOwogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICBzdW1hPTA7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICAgICAgZG9kYXdhbmllKHN1bWEsbGljemJhMSk7CgogICAgICAgIGlmKHN1bWEpCiAgICAgICAgICAgIGNvdXQgPDwgIk5JRSIgPDwgZW5kbDsKICAgICAgICBlbHNlCiAgICAgICAgICAgIGNvdXQgPDwgIlRBSyIgPDwgZW5kbDsKICAgIH0KICAgIHJldHVybiAwOwp9Cgp2b2lkIGN6eV9wYXJ6eXN0YShpbnQgJmxpY3piYTEsIGJvb2wgJnN1bWEpCnsKICAgIGlmKGxpY3piYTElMj09MCkKICAgICAgICBzdW1hPTA7CiAgICBlbHNlCiAgICAgICAgc3VtYT0xOwp9Cgp2b2lkIGRvZGF3YW5pZShib29sICZzdW1hLCBpbnQgJmxpY3piYTEpCnsKICAgIGlmKChzdW1hPT0wICYmIGxpY3piYTElMj09MCl8fChzdW1hPT0xICYmIGxpY3piYTElMj09MSkpCiAgICAgICAgc3VtYT0wOwogICAgZWxzZQogICAgICAgIHN1bWE9MTsKfQoKdm9pZCBtbm96ZW5pZShpbnQgJmxpY3piYTEsIGludCAmbGljemJhMikKewogICAgaWYobGljemJhMSUyPT0xICYmIGxpY3piYTIlMj09MSkKICAgICAgICBsaWN6YmExPTE7CiAgICBlbHNlCiAgICAgICAgbGljemJhMT0wOwp9Cgp2b2lkIG1ub3plbmllKGJvb2wgJnN1bWEsIGludCAmbGljemJhMSkKewogICAgaWYoc3VtYSUyPT0xICYmIGxpY3piYTElMj09MSkKICAgICAgICBzdW1hPTE7CiAgICBlbHNlCiAgICAgICAgc3VtYT0wOwp9Cg==