31458번 - !!초콜릿 중독 주의!!

문제

코코의 초콜릿 가게에서 파는 초콜릿은 달달하기로 유명하다. 그래서 코코는 아래와 같은 경고문을 가게 앞에 붙이려고 한다.

!!초콜릿 중독 주의!!

이 문구를 유심히 보던 코코는 느낌표 사이의 문장을 지우고 그 자리에 수를 넣으면 일종의 수식이 된다는 사실을 깨달았다. 이 수식을 계산해 보자.

이 문제에서 계산할 수식은 정수 하나와 0ドル$개 이상의 느낌표로 이루어져 있다. 정수는 0ドル$ 또는 1ドル$이며, 느낌표는 정수의 앞이나 뒤에 올 수 있다. 이 수식을 계산하는 규칙은 다음과 같다.

• $n!$은 $n$의 팩토리얼이다. 0ドル!=1,ドル 1ドル!=1$로 정의된다.
• $!n$은 $n$의 논리 반전(logical not)이다. $!0=1,ドル $!1=0$으로 정의된다.
• 팩토리얼이나 논리 반전이 중첩되어 있으면 중첩된 횟수만큼 계산하며, $!n!$과 같이 둘 다 사용된 경우에는 팩토리얼을 먼저 계산한다. 예를 들어, $!!n!!=!(!((n!) !))$이다.

입력

첫 번째 줄에는 수식의 개수 $T$가 주어진다. $(1\le T\le 1,円 000)$

두 번째 줄부터 $T$개의 수식이 한 줄에 하나씩 주어진다. 하나의 수식은 $a$개의 느낌표, 정수 $n,ドル $b$개의 느낌표가 공백 없이 순서대로 합쳐진 형태이다. $(0\le a,b\le 30;$ 0ドル\le n\le 1)$

출력

각 수식을 계산한 결과를 한 줄에 하나씩 출력한다.

제한

힌트