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