ビット演算方程式（★★★★★）

問題文

数字、文字 x 、括弧 ( , ) 、記号 | , ^ , & , = からなる $x$ についての方程式が文字列 $S$ として与えられます。

ここで方程式は、以下のBNFによって定義される <Equation> です。

文字と記号はそれぞれ以下のように説明されます。

• x：変数 $x$ 。ただし、$x$ は $0$ 以上の整数である。
• |：ビットごとの論理和 $\mathrm{or}$ 。
• ^：ビットごとの排他的論理和 $\mathrm{xor}$ 。ただし、 $\mathrm{or}$ よりも先に計算される。
• &：ビットごとの論理積 $\mathrm{and}$ 。ただし、 $\mathrm{or}, \mathrm{xor}$ よりも先に計算される。
• =：等号 $=$ 。

例えば、以下の例は <Equation> になり得ます。

• 4|1^3&x=7 ： $4 ~ \mathrm{or} ~ 1 ~ \mathrm{xor} ~ 3 ~ \mathrm{and} ~ x = 7$ , 計算順序は $4 ~\mathrm{or}~ (3 ~ \mathrm{xor} ~ (1 ~\mathrm{and}~ x))$ であることに注意。
• (x|1)&((3^x)&15)=1073741823 ： $(x ~\mathrm{or}~ 1) ~\mathrm{and}~ ((3 ~\mathrm{xor}~ x) ~\mathrm{and}~ 15) = 1073741823$
• (((x)))=314 ： $(((x))) = 314$
• 1=2 ： $1 = 2$

ただし、以下の例は <Equation> になり得ません。

• x=-1
• x=9999999999
• 2x=4
• 123=x
• x=3=3

$x$ についての方程式の解の最小値を求めてください。ただし、解が存在しない場合は -1 を出力してください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• $T$ は $1 \leqq T \leqq 100$ を満たす整数
• $S$ は問題文中のBNFで定義された <Equation> である
• $1 \leqq |S| \leqq 2000$

入力

入力は以下の形式で標準入力から与えられます。ここで、$\mathrm{case}_i$ は $i$ 番目のテストケースです。

各テストケースは以下の形式で与えられます。

出力

標準出力に $T$ 行出力し、$i$ 行目には $i$ 番目のテストケースについての答えを出力してください。

各テストケースについて、$x$ についての方程式の解の最小値を出力してください。ただし、解が存在しない場合は -1 を出力してください。

サンプル

5
4|1^3&x=7
4&(3|x)=6
x^x|x&x=100
1=2
x|(x&(x|(x^1234)^5678)|9012)=13301

2
-1
100
-1
4289

この入力では $5$ 個のテストケースが与えられています。$1, 2, 3, 4$ 番目のテストケースについて、以下のことが言えます。

• $4 ~\mathrm{or}~ 1 ~ \mathrm{xor} ~ 3 ~ \mathrm{and} ~ x = 7$ の解のうち最小のものは $x = 2$ です。

• $4 ~\mathrm{and}~ (3 ~\mathrm{or}~ x) = 6$ を満たす $x$ は存在しません。この場合、-1 を出力してください。

• $x ~ \mathrm{xor} ~ x ~\mathrm{or}~ x ~\mathrm{and}~ x = 100$ の解は $x = 100$ です。方程式の中に $x$ が複数個含まれている場合もあります。

• $1 = 2$ を満たす $x$ は存在しません。方程式の中に $x$ が含まれない場合もあります。