Вирази

Арифметичні вирази зазвичай записуються з операторами між двома операндами, що називається інфіксною нотацією. Наприклад, (x + y) * (z - w) - це арифметичний вираз в інфіксній нотації. Проте, легше написати програму для обчислення значення виразу, коли він записаний у постфіксній нотації (також відомій як зворотна польська нотація). У постфіксній нотації оператор записується після своїх двох операндів, які самі можуть бути виразами. Наприклад, x y + z w - * є постфіксною нотацією для наведеного вище виразу. Зверніть увагу, що для такого запису дужки не потрібні.

Для обчислення виразу в постфіксній нотації використовується алгоритм, що працює зі стеком. Стек - це структура даних, яка підтримує дві операції:

1. push: число додається на верх стека.

2. pop: число знімається з вершини стека.

Під час обчислення вираз обробляється зліва направо. Якщо зустрічається число, його кладуть у стек. Якщо зустрічається оператор, витягуються два числа зі стека, до них застосовується оператор, і результат повертається в стек. Наступний псевдокод обробляє оператор O:

a := pop();

b := pop();

push(b O a);

Результатом виразу буде єдине число, що залишиться в стеці.

Припустимо, що замість стека ми використовуємо чергу. Черга також має операції push і pop, але їх значення трохи інше:

1. push: число додається в кінець черги.

2. pop: число витягується з початку черги.

Чи можете ви переписати заданий вираз так, щоб алгоритм, що використовує чергу для його обчислення, давав той самий результат, що й алгоритм зі стеком?

Вхідні дані

Перше число містить число t (t ≤ 200). Кожен з наступних t рядків містить один вираз у постфіксному записі. Арифметичні операції позначаються великими літерами, числа - малими літерами. Довжина кожного виразу менше 10000 символів.

Вихідні дані

Для кожного вхідного рядка виведіть вираз, результат якого буде таким самим, якщо використовувати в алгоритмі чергу замість стека. Щоб результат визначався однозначно, вважайте, що задані оператори не є асоціативними або комутативними.

Приклади