asd

#include <bits/stdc++.h>
using namespace std;
stack<long long> st;
long long res = 0, flag = 0, t, a, b, MOD = 123456789;
string s;
long long module(long long a){
    return (a%MOD+MOD)%MOD;
}
long long solve(string s){
    res = 0; flag = 0;
    if(!isdigit(s[0])){
        flag = 3;
        if(s[0] == '+') st.push(module(s[1]-48));
        else st.push(module((-1)*(s[1]-48)));
    }
    for(long long i = flag; i < s.size(); i+=2){
        if(i==0) st.push(module(s[i]-48));
        else if(s[i-1] != '*'){
            if(s[i-1] == '+') st.push(module(s[i]-48));
            else st.push(module(((s[i]-48)*(-1))));
        }
        else{
            st.push(module((s[i]-48)));
            a = module(st.top()); st.pop();
            b = module(st.top()); st.pop();
            st.push(module(a*b));
        }
    }
    while(!st.empty()){
        a = module(st.top()); st.pop();
        res += module(a);
    }
    return module(res);
}
int main(){
    freopen("gay.txt", "r", stdin);
    cin >> t;
    for(long long i = 0; i!= t; i++){
        cin >> s;
        cout << solve(s) << "\n";
    }
    return 0;
}