Little X has $n$ pairs of positive integers $(a_i, b_i)$ ($1 \le i \le n$). He maintains a multiset $S$, initially empty, and performs $n$ rounds of operations. In the $i$-th round ($1 \le i \le n$), he adds $a_i$ copies of $b_i$ to $S$.

Let $m = \sum_{i=1}^n a_i$. After all operations are completed, Little X obtains a multiset $S$ containing $m$ positive integers. Finally, he calculates the median of $S$, which is the $\lfloor \frac{m+1}{2} \rfloor$-th smallest number in $S$, as his lucky number.

Little Y, who wants to know Little X's lucky number, does not know the specific values of these $n$ pairs, but she knows the range for each number. Specifically, for each $1 \le i \le n$, Little Y knows $a_i \in [l_{i,1}, r_{i,1}]$ and $b_i \in [l_{i,2}, r_{i,2}]$.

Little Y wants to know how many numbers can possibly be Little X's lucky number, given the conditions above.

Input

Read the data from the file lucky.in.

This problem contains multiple test cases. The first line contains two integers $c$ and $T$, representing the test case ID and the number of test cases, respectively. Then, each test case is provided. The sample satisfies $c = 0$.

For each test case, the first line contains an integer $n$, representing the number of pairs. The next $n$ lines each contain four integers $l_{i,1}, r_{i,1}, l_{i,2}, r_{i,2}$, describing the range for each number in the $i$-th pair.

Output

Output to the file lucky.out.

For each test case, output a single integer on a single line, representing the number of possible lucky numbers.

Examples

Input 1

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

Output 1

1
2
4
3

Note

There are 4 test cases in this sample.

• For the first test case, if we choose $(a_1, b_1) = (1, 1)$ and $(a_2, b_2) = (1, 2)$, we get $S = \{1, 2\}$, where the median is 1; if we choose $(a_1, b_1) = (2, 1)$ and $(a_2, b_2) = (1, 2)$, we get $S = \{1, 1, 2\}$, where the median is 1. Therefore, only 1 is a possible median, so the answer is 1.
• For the second test case, if we choose $(a_1, b_1) = (1, 1)$ and $(a_2, b_2) = (1, 2)$, we get $S = \{1, 2\}$, where the median is 1; if we choose $(a_1, b_1) = (1, 2)$ and $(a_2, b_2) = (1, 3)$, we get $S = \{2, 3\}$, where the median is 2. It can be proven that no other medians can be calculated, so the answer is 2.
• For the third test case, it can be proven that 1, 2, 3, and 4 are the only possible medians, so the answer is 4.
• For the fourth test case, it can be proven that 1, 2, and 3 are the only possible medians, so the answer is 3.

Subtasks

Let $\sum n$ be the sum of $n$ over all test cases in a single test point. For all test points:

• $1 \le T \le 400$
• $1 \le n \le 2 \times 10^5$, $1 \le \sum n \le 6 \times 10^5$
• $\forall 1 \le i \le n, 1 \le l_{i,1} \le r_{i,1} \le 10^9, 1 \le l_{i,2} \le r_{i,2} \le 10^9$

Special Property A: $\forall 1 \le i \le n, r_{i,1}, r_{i,2} \le n$. Special Property B: $\forall 1 \le i \le n, l_{i,1} = r_{i,1}$.