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$$$.

✓	#	Name		✎	Rating↕	Solved↕
	2239F	Colorful Works dp fft games implementation			3500	194
	1991H	Prime Split Game bitmasks dp fft games math number theory			3300	580

Problemset