小 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_i1, r_i1] 且 b_i \in [l_i2, r_i2]。

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

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

对于每组测试数据，第一行一个整数 n，表示二元组的个数，接下来 n 行，第 i (1 \leq i \leq n) 行四个整数 l_i1, r_i1, l_i2, r_i2，描述二元组每个数的范围。

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

该组样例共有 4 组测试数据。

• 对于第一组测试数据，若取 (a_1, b_1) = (1, 1), (a_2, b_2) = (1, 2)，则得到 S = {1, 2}，其中位数为 1；若取 (a_1, b_1) = (2, 1), (a_2, b_2) = (1, 2)，则得到 S = {1, 1, 2}，其中位数为 1。因此仅有 1 为可能计算出的中位数，因此答案为 1。
• 对于第二组测试数据，若取 (a_1, b_1) = (1, 1), (a_2, b_2) = (1, 2)，则得到 S = {1, 2}，其中位数为 1；若取 (a_1, b_1) = (1, 2), (a_2, b_2) = (1, 3)，则得到 S = {2, 3}，其中位数为 2。可以证明不存在其他可能计算出的中位数，因此答案为 2。
• 对于第三组测试数据，可以证明有且仅有 1, 2, 3, 4 为可能计算出的中位数，因此答案为 4。
• 对于第四组测试数据，可以证明有且仅有 1, 2, 3 为可能计算出的中位数，因此答案为 3。

设 \sum n 为单个测试点内所有测试数据的 n 的和。对于所有测试点，

• 1 \leq T \leq 400，
• 1 \leq n \leq 2 \times 10^5，1 \leq \sum n \leq 6 \times 10^5，
• \forall 1 \leq i \leq n，1 \leq l_i1 \leq r_i1 \leq 10^9，1 \leq l_i2 \leq r_i2 \leq 10^9。

联合省选