Difference Pyramid

$0,1,2$로만 이루어진 길이 $N$의 배열 $A=[A_1,A_2,\cdots,A_N]$이 주어진다.

배열의 길이가 $1$이 될 때까지 다음 연산을 반복한다.

현재 배열의 길이가 $L$이라 하자. 길이 $L-1$의 새 배열 $B$를

로 정의하고, 배열 $A$를 $B$로 바꾼다.

마지막에 남는 하나의 원소를 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스는 다음과 같은 형식으로 주어진다.

$N$ $A_1\ A_2\ \cdots\ A_N$

각 테스트 케이스마다 마지막에 남는 원소를 한 줄에 출력한다.

• $1\leq T\leq200$.
• $1\leq N\leq1\,000\,000$.
• $0\leq A_i\leq2$ ($1\leq i\leq N$).
• 모든 테스트 케이스에 대한 $N$의 합은 $1\,000\,000$ 이하이다.