#include <bits/stdc++.h>
using namespace std;
vector <string> onp;
vector <string> dzialania;
vector <long long> wynik;
const int q=10007;
bool czy_znak(string znak)
{
    if(znak=="+" || znak=="*" || znak=="^" || znak=="(" || znak==")")
    return true;
    else
    return false;
}
void znakowe(string znak)
{
    if(znak=="+")
    {
        while(!dzialania.empty() && (dzialania.back()=="*" || dzialania.back()=="^") )
        {
            onp.push_back( dzialania.back() );
            dzialania.pop_back();
        }
        dzialania.push_back(znak);
    }
    else if(znak=="*")
    {
        while(!dzialania.empty() && dzialania.back()=="^")
        {
            onp.push_back( dzialania.back() );
            dzialania.pop_back();
        }
        dzialania.push_back(znak);
    }
    else if(znak=="^")
    {
        dzialania.push_back(znak);
    }
    else if(znak=="(")
    {
        dzialania.push_back(znak);
    }
    else if(znak==")")
    {
        while( !dzialania.empty() && dzialania.back()!="(")
        {
            onp.push_back( dzialania.back() );
            dzialania.pop_back();
        }
        dzialania.pop_back();
        if(!dzialania.empty())
        {
            onp.push_back( dzialania.back() );
            dzialania.pop_back();
        }
    }
}
long long potegowanie(long long  a, long long  k, int q)
{
  if (a==0 && k==0) return 1;
  if(k==0) return 1;
  else if(k%2==0) return (potegowanie(a, k/2, q)*(potegowanie(a, k/2, q)))%q;
  else return (a*(potegowanie(a, (k-1), q)))%q;
}
long long  dzialaj(long long a, long long b, string znak)
{
    if(znak=="+")
    {
        return (a+b)%q;
    }
    else if (znak=="*")
    {
        return (a*b)%q;
    }
    else if(znak=="^")
    {
        return potegowanie(b, a , q)%q;
    }
}
int main()
{
    int z;
    cin>>z;
    for(int i=0; i<z; i++)
    {
        int dlugosc;
        string znak;
        cin>>dlugosc;
        for(int j=0; j<dlugosc; j++)
        {
            cin>>znak;
            if(czy_znak(znak))
            {
                znakowe(znak);
            }
            else
            {
                onp.push_back(znak);
            }
        }
        while(!dzialania.empty())
        {
            onp.push_back( dzialania.back() );
            dzialania.pop_back();
        }
        for(int j=0; j<onp.size(); j++)
        {
            if(j>0)
            {
                cout<<" ";
            }
            cout<<onp[j];
        }
        cout<<endl;
        for(int j=0; j<onp.size(); j++)
        {
            if( czy_znak(onp[j]) )
            {
                long long a=wynik.back();
                wynik.pop_back();
                long long b=wynik.back();
                wynik.pop_back();
                wynik.push_back( dzialaj(a, b, onp[j] ) );
            }
            else
            {
                long long  x=atoi(onp[j].c_str());
                wynik.push_back(x%q);
            }
        }
        wynik[0]%=q;
        cout<<wynik[0]<<endl;
        wynik.clear();
        onp.clear();
        dzialania.clear();

    }
}