Given a function ~f(x)~ that receives an array ~x = (x_0, x_1, \dots, x_{19})~ of 20 positive integers. The function ~f(x)~ is represented in the form:

~f(x) = x_0 \ ?_0 \ x_1 \ ?_1 \ x_2 \ ?_2 \ \dots \ ?_{18} \ x_{19}~

Where each operator ~?_i~ (~0 \le i \le 18~) represents a fixed binary operation belonging to the following set of operations:

• Addition (+), Subtraction (-), Multiplication (*), Modulo (%)
• Exponentiation (power or ~a^b~)
• Floor division (floor or ~\lfloor a / b \rfloor~)
• Ceil division (ceil or ~\lceil a / b \rceil~)
• Bitwise AND (&), Bitwise OR (|), Bitwise XOR (^)

Evaluation Order

The expression is evaluated according to the following operator precedence (from highest to lowest):

1. Exponentiation (power)
2. Multiplication (*), Floor Division (floor), Ceil Division (ceil), Modulo (%)
   (evaluated from left to right)
3. Addition (+) and Subtraction (-)
   (evaluated from left to right)
4. Bitwise AND (&)
5. Bitwise XOR (^)
6. Bitwise OR (|)

Operators with the same precedence are evaluated from left to right.

Determine the underlying rule of the operators and answer ~T~ queries. For each query, compute the value of ~f(x)~.

Input Specification

The first line contains a positive integer ~T~ — the number of queries.

Each of the next ~T~ lines contains 20 space-separated positive integers ~x_0, x_1, \dots, x_{19}~.

Output Specification

Print ~T~ lines, each containing a single integer — the value of ~f(x)~ for the corresponding query.

Constraints

• ~1 \le T \le 1000~
• ~1 \le x_i \le 1000~

Sample Input

10
23 20 21 37 29 22 11 19 12 40 37 27 18 25 30 19 21 39 26 12
14 37 26 31 23 23 39 36 27 15 40 32 32 33 19 39 25 20 20 18
10 27 37 32 23 10 37 32 27 17 11 38 20 15 23 31 14 28 13 14
34 33 12 19 28 38 20 37 40 14 35 28 32 12 27 30 16 13 25 21
23 35 28 33 27 34 35 24 18 19 13 30 14 27 18 23 29 25 19 32
12 37 26 32 36 31 24 34 37 13 23 10 12 29 14 24 13 12 18 35
19 31 34 26 26 18 24 33 31 22 34 21 26 29 21 33 16 39 26 28
11 20 31 37 20 12 30 40 23 26 12 10 31 24 12 32 24 29 18 28
25 40 32 34 13 20 24 38 11 39 35 17 29 10 12 34 36 22 29 11
30 37 17 19 12 28 16 28 34 15 18 32 39 23 33 28 35 14 35 34

Sample Output

233173817337089314743651192201462430251834
70703566310433775300908169505361477397622073692148
43577423756817226703444498233744488595622
8716734153676513838483076641586610108993664
35047277617513292732559665286
26623333349604720618
339288760899451875889011331255855889988401
13083333562061752139839557911314053
854732332361525803601765998864910778393
129733990798125012408604775185719085760513