#366 Difference Pyramid

Statement

Statement language

You are given an array $A=[A_1,A_2,\cdots,A_N]$ of length $N$ , consisting only of $0$ , $1$ , and $2$ .

Repeat the following operation until the length of the array becomes $1$ .

Suppose the current length is $L$ . Construct a new array $B$ of length $L-1$ by

B_i=|A_{i+1}-A_i|\qquad(1\leq i<L),

and replace $A$ with $B$ .

Find the single value that remains at the end.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each test case, print the final remaining value on one line.

#	Score	Constraints
1	19	$N\leq2\,000$ . The sum of $N$ over all test cases does not exceed $4\,000$ .
2	33	$A_{i} \leq 1$ ().

Input

1
4
0 2 1 0

Output

1

The array changes as follows.

$0\ 2\ 1\ 0$ $2\ 1\ 1$ $1\ 0$ $1$

Therefore, the final remaining value is .