A93080.「联合省选 2025」幸运数字

小 X 有 $n$ 个正整数二元组 $(a_i, b_i)$ $(1 \leq i \leq n)$。他将会维护初始为空的可重集 $S$，并对其进行 $n$ 轮操作。第 $i$ $(1 \leq i \leq n)$ 轮操作中，他会在 $S$ 中加入 $a_i$ 个 $b_i$。

设 $m = \sum \limits_{i=1}^{n} a_i$，在所有操作结束后，小 X 会得到一个包含 $m$ 个正整数的可重集 $S$。最后他会计算 $S$ 的中位数，即 $S$ 中第 $\left\lfloor \frac{m+1}{2} \right\rfloor$ 小的数，作为他的幸运数字。

想知道小 X 幸运数字的小 Y 不知道这 $n$ 个二元组的具体数值是多少，但她得知了每个数的范围。具体地，对于每个 $1 \leq i \leq n$，小 Y 知道 $a_i \in [l_{i,1}, r_{i,1}]$ 且 $b_i \in [l_{i,2}, r_{i,2}]$。

小 Y 想知道在满足以上条件的情况下，有多少个数可能成为小 X 的幸运数字。

从文件 lucky.in 中读入数据。

本题有多组测试数据。输入的第一行两个整数 $c, T$，分别表示测试点编号和测试数据组数，接下来输入每组测试数据。样例满足 $c = 0$。

对于每组测试数据，第一行一个整数 $n$，表示二元组的个数，接下来 $n$ 行，第 $i$ $(1 \leq i \leq n)$ 行四个整数 $l_{i,1}, r_{i,1}, l_{i,2}, r_{i,2}$，描述二元组每个数的范围。

输出到文件 lucky.out 中。

对于每组测试数据，输出一行一个整数，表示可能的幸运数字个数。