Problem Description
Carelessly designed cryptographic primitives leave your secret as bared as plain text. It is not a surprise that seemingly "random" hash functions are weak. Consider the function of the following form:
unsigned int hash(unsigned int x) {
x += 0x327b7473u;
x &= 0xffffafffu;
x ^= 0x90283712u;
x |= 0x00300000u;
x += 0x89129723u;
x ^= 0x464726ccu;
x &= 0xfffff8ffu;
//......
return x;
}
The function maps an integer to another integer and intends to make the result random. All statements are of the form: x (some operator) (some number). Possible operators are: add (+=), subtract (-=), bitwise-and (&=), bitwise-xor (^=), and bitwise-or (|=). Due to the nature of fixed size integer, there is an implicit modulo 4294967296 operation after each statement.
However, it is a rather weak hash function from a cryptographic point of view. To demonstrate its weakness, you are requested to find an input x that maximizes the output.
In this example the best x is 1841992591 and the maximum output is 4292342015.
Input
The first line contains an integer T, denoting the number of the test cases.
Each test case begins with a non-negative integer N, the number of operations in the hash function. 0<=N<=40.
Then follows N lines, each describing an operation. Each line contains an operator and an 8-digit hexadecimal number.
Output
For each test case, output the maximum output in decimal format.
Sample Input
2
7
+= 327b7473
&= ffffafff
^= 90283712
|= 00300000
+= 89129723
^= 464726cc
&= fffff8ff
1
-= 00000001
