Coco's chocolate shop is famous for its sweet chocolates. Because of this, Coco wants to put the following warning sign in front of the shop:

While looking closely at this phrase, Coco realized that if you erase the sentence between the exclamation marks and put a number in its place, it becomes a kind of mathematical expression. Let's calculate this expression.

The expression to be calculated in this problem consists of one integer and zero or more exclamation marks. The integer is either $0$ or $1$, and exclamation marks can appear before or after the integer. The rules for calculating this expression are as follows:

• $n!$ is the factorial of $n$. It is defined as $0! = 1$ and $1! = 1$.
• $!n$ is the logical NOT of $n$. It is defined as $!0 = 1$ and $!1 = 0$.
• If factorials or logical NOTs are nested, they are calculated as many times as they are nested. If both are used, such as in $!n!$, the factorial is calculated first. For example, $!!n!! = !(!((n!)!))$.

Input

The first line contains the number of expressions $T$. $(1 \le T \le 1\,000)$

From the second line, $T$ expressions are given, one per line. Each expression is in the form of $a$ exclamation marks, an integer $n$, and $b$ exclamation marks, concatenated without spaces. $(0 \le a, b \le 30;$ $0 \le n \le 1)$

Output

Print the result of each expression calculation, one per line.

Examples

Input 1

6
0!
1!
!0
!1
!!0!!
!!1!!

Output 1

1
1
1
0
1
1