题目背景

Problem Number: $\textit{45}$

众所周知，区间操作问题应该求出区间和、最大值等值。但今天小 F 有个不情之请。

题目描述

小 F 正在研究斐波那契数列，他惊讶地发现，可以把这种数列 $F$ 的定义式略作修改，得到 $\digamma$ 数列：

$$\digamma(x)=\{1,1,-1,-1,1,1,-1,-1,1,\ldots\}$$

注意到 $\digamma$ 数列具有周期性，最小正周期 $T=4$。

请注意这里 $\digamma$ 数列与数学上用其表示的双伽玛函数的区别。

小 F 找到一个长度为 $n$ 的数列 $a$，他每次对其进行如下操作：

• 选定两个整数 $l,r$，满足 $1\le l\le r\le n$。
• 对于每个满足 $l\le i\le r$ 的 $i$，将 $a_i$ 加上 $\digamma(i-l+1)$。
• 记录下本次操作（即第 $j$ 次操作）的选定区间的长度 $len_j=r-l+1$。

他一共进行了 $m$ 次操作，操作后得到数列记作 $b$，同时记 $sum=\sum_{i=1}^mlen_i$。

不幸的是，小 F 把 $sum$ 和数列 $len$ 都弄丢了，他只记得 $n$ 和数列 $a,b$。

现在，他想请你根据这些信息，求出 $sum$ 的奇偶，即 $\textbf{\textit{sum}}$ 对 $\textbf2$ 取模后的值。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

接下来 $3\cdot T$ 行，描述每组数据。对于每组数据：

• 第一行一个整数 $n$。
• 第二行 $n$ 个整数，描述数列 $a$。
• 第三行 $n$ 个整数，描述数列 $b$。

数据保证数列 $a$ 一定可以经过若干操作变为数列 $b$。

输出格式

对于每组数据，输出仅一行一个数，即 $sum$ 对 $2$ 取模后的值。

1
4
1 2 3 4
2 4 3 4

1

提示

样例 1 说明

注意到可能进行的是如下操作：

• 第 $1$ 次操作选定 $l=2,r=3$，则数列变成 $[1,{\underline\color{red}\textbf3},{\underline\color{red}\textbf4},4]$。此时 $len_1=2$。
• 第 $2$ 次操作选定 $l=1,r=3$，则数列变成 $[{\underline\color{red}\textbf2},{\underline\color{red}\textbf4},{\underline\color{red}\textbf3},4]$。此时 $len_2=3$。

则 $sum=len_1+len_2=5$，是奇数。故 $sum\bmod 2=1$。

数据规模与约定

本题采用捆绑测试

$$\newcommand{\arraystretch}{1.5} \begin{array}{c|c|c|c}\hline\hline \textbf{Subtask} & \bm{\sum n\le} & \textbf{特殊性质} & \textbf{分值} \\\hline \textsf{1} & \le 10 & a_i,b_i\le 10^9 & 10 \\\hline \textsf{2} & \le 10^3 & a_i,b_i\le 10^9 & 20 \\\hline \textsf{3} & \text{无特殊限制} & a_i,b_i\le 10^9 & 20 \\\hline \textsf{4} & \text{无特殊限制} & a_i\le b_i & 20 \\\hline \textsf{5} & \text{无特殊限制} & - & 30 \\\hline\hline \end{array} $$

对于 $100\%$ 的数据，有 $1\le T\le 10^3$，$1\le n\le 10^5$，$1\le a_i,b_i\le 10^{18}$。

单个测试点内保证 $\sum n\le 2\times 10^5$。

说明

$\digamma$ 数列拥有如下的递推式：

$$\digamma(x)= \begin{cases} 1,&x\le 2\\ -1,&x=3\\ \digamma(x-1)-\digamma(x-2)+\digamma(x-3),&x>3. \end{cases} $$