给定 $n$ 个数对 $(l_i, r_i)$，你需要计算有多少个大小为 $n$ 的排列 $p$ 满足 $l_i \le p_i \le r_i$。 你只需要输出答案对 $2$ 取模的结果。

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 10^6$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示需要计算的排列 $p$ 的大小。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i, r_i$ ($1 \le l_i \le r_i \le n$)。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出一个整数，表示答案对 $2$ 取模的结果。

样例

样例输入 1

4
5
1 2
1 5
1 2
1 2
2 2
5
1 1
2 4
2 3
5 5
3 4
5
3 5
1 2
3 4
3 5
3 3
5
1 5
1 4
4 5
5 5
1 2

样例输出 1

0
1
0
0