F. Colorful Works

Source: Codeforces 2239F
Contest: Codeforces Round 1105 (Div. 1)
Time limit: 5 seconds
Memory limit: 256 megabytes

Statement

Gold14526 is a painter. He can paint with $n$ colors, numbered $1, 2, \ldots, n$. Color $i$ has a constraint interval $[l_i, r_i]$.

A work is defined as a rooted tree $T=(V,E)$ where every edge is colored (with one of the $n$ colors). A work is called colorful if the following conditions are satisfied:

• For any three nodes $u, v, w \in V$, if edges $(u,v)$ and $(v,w)$ both exist, they must have different colors.
• For all colors $i \in [1,n]$, let $d(u,i)$ denote the number of edges of color $i$ on the simple path from node $u$ to the root. Then $\max_{u \in V} d(u,i) \in [l_i, r_i]$.

Two works $T=(V,E)$ and $T'=(V',E')$ are defined as isomorphic if and only if the following two conditions are met:

• $\lvert V\rvert = \lvert V'\rvert$;
• There exists a bijection $f:V \to V'$ such that:
• Let $r$ be the root of $T$ and $r'$ be the root of $T'$. Then $f(r) = r'$;
• For any $(u,v) \in E$, we have that $(f(u),f(v)) \in E'$, and the color of edge $(u,v)$ is the same as the color of edge $(f(u),f(v))$.

Gold14526 wants to know the maximum number of colorful works he can choose such that the works are pairwise non-isomorphic. Output the answer modulo $\bf2$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1\le n\le 2\cdot 10^6$) — denoting the number of colors.

The following $n$ lines each contain two integers, the $i$ -th of them $l_i$ and $r_i$ ($0\le l_i\le r_i\le 2\cdot 10^5$, $r_i\ge 1$) — denoting the constraint interval of the $i$ -th color.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^6$.

Let $m=\max_{i=1}^n r_i$. Then it is guaranteed that the sum of $m$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output $0$ or $1$, representing the maximum number of works that can be chosen modulo $2$.

Note

In the first test case, the constraints for both colors are $[0, 1]$. This means on any simple path from the root, there can be at most $1$ edge of color $1$ and at most $1$ edge of color $2$. There are exactly $9$ valid pairwise non-isomorphic trees:

• $1$ tree with $1$ node: just the root.
• $2$ trees with $2$ nodes: the root is connected to a child by an edge of color $1$, or by an edge of color $2$.
• $3$ trees with $3$ nodes:
• the root is connected to two children by edges of color $1$ and $2$ respectively.
• a path of $2$ edges from the root, colored $1$ then $2$.
• a path of $2$ edges from the root, colored $2$ then $1$.
• $2$ trees with $4$ nodes:
• the root has a child via color $1$ (which further has a child via color $2$), and another child via color $2$.
• the root has a child via color $2$ (which further has a child via color $1$), and another child via color $1$.
• $1$ tree with $5$ nodes: the root is connected to two children by colors $1$ and $2$, and each of these children has exactly one child of the opposite color.

Since $9 \equiv 1 \pmod 2$, the output is $1$. In the second test case, the constraints for both colors are $[1, 1]$. Every valid tree must satisfy the maximum count of each color on the paths to be exactly $1$. Therefore, the tree must contain at least one edge of color $1$ and at least one edge of color $2$. There are exactly $6$ valid trees:

• $3$ trees with $3$ nodes: the root connected to two children by colors $1$ and $2$; a path colored $1$ then $2$; a path colored $2$ then $1$.
• $2$ trees with $4$ nodes: same as the two $4$-node trees described in the first test case.
• $1$ tree with $5$ nodes: same as the $5$-node tree described in the first test case.

Since $6 \equiv 0 \pmod 2$, the output is $0$.

Examples

4
2
0 1
0 1
2
1 1
1 1
3
0 2
0 1
0 1
3
1 2
1 1
1 1

1
0
1
1