Aritmética explosiva

Na Academia de Código Macaco (ACM), Trudy escreveu diversas versões do icônico "Hello, world!", em 17 linguagens de programação diferentes, e então percebeu que havia um defeito comum a todas elas: são previsíveis demais!

Adepta ao código ninja, Trudy decidiu criar sua própria linguagem de programação para resolver esse problema. Ocupada com a otimização de recursão em seu compilador experimental, Trudy pediu que você escrevesse um reconhecedor de expressões aritméticas, que avaliasse resultados extraordinários.

Para agradar Trudy, você decidiu ignorar as convenções matemáticas, e escolher uma ordem de precedência e associativadade para os operadores aritméticos, de tal modo a maximizar o resultado avaliado para uma expressão aritmética! Dessa forma os operadores podem ser executado da direita para a esquerda, ou vice versa, sempre tentando maximizar o resultado.

Trudy não escolhe ordens de precedência e associatividade que ocorram divisões por zero ou overflow em seus inteiros de 32 bits.

Seu protótipo usa C como representação intermediária, pois o Grande Compactador de Código (GCC) está sendo usado para a geração de executáveis. Desse modo a divisão de $3/2$ resulta em $1$, e $-3/2$ resulta em $-1$.

Na primeira linha é dado a quantidade de casos de teste $t$ $(1 <= t <= 10^4)$.

Cada caso de teste consiste em duas linhas.

A primeira linha de um caso de teste indica a quantidade de operandos $n$ $(2 <= n <= 10^3)$.

A segunda linha de um caso de teste é a expressão aritmética a ser reconhecida e avaliada, na forma $a_1~op_1~a_2~op_2~...~op_{n-1}~a_n$.

Os $n$ operandos $a_i$ $(a_1, a_2, ..., a_n)$ são números inteiros $(-10^3 <= a_i <=10^3)$.

Os $n-1$ operadores $op_i$ $(op_1, op_2, ..., op_{n-1})$ são um dos seguintes caracteres: '+', '-', '*' e '/', que correspondem respectivamente a soma, subtração, multiplicação e divisão.

Note que não há espaços entre operandos e operadores.

É garantido que a soma de $n$ em todos casos de teste não ultrapassa $10^5$.

Para cada caso de teste, imprima o valor máximo que se pode avaliar escolhendo a ordem de precedência e associatividade entre as operações aritméticas.

A ordem de precedência e associatividade escolhida para um caso de teste é independente dos demais.