4999：Overt

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.

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.

For each test case, output the maximum output in decimal format.