Description

ACM（ACMers' Chatting Messenger）是 Marjar 科技公司开发的一款著名的即时通讯软件。为了吸引更多用户，Marjar 公司的老板 Edward 最近为该软件新增了一个功能。该功能的描述如下：

如果两个用户 $A$ 和 $B$ 在最近连续 $m$ 天内，$\textbf{每天都互相发送了消息}$，则他们之间的“友谊值”会增加 $1$。

更正式地说，如果用户 $A$ 在第 $(i-m+1)$ 天到第 $i$ 天（包括这两天）中，每天都给用户 $B$ 发送了消息，并且用户 $B$ 在同样的时间段内也每天都给用户 $A$ 发送了消息，那么在第 $i$ 天结束时，他们之间的“友谊值”将增加 $1$。

现已知用户 $A$ 和 $B$ 在连续 $n$ 天内的聊天记录，请问在第 $n$ 天结束时他们之间的友谊值是多少（已知初始友谊值为 $0$）？

Input Format

有多组测试数据。输入的第一行包含一个整数 $T$（$1 \le T \le 10$），表示测试数据的组数。对于每组测试数据：

第一行包含四个整数 $n$（$1 \le n \le 10^9$）、$m$（$1 \le m \le n$）、$x$ 和 $y$（$1 \le x, y \le 100$）。$n$ 和 $m$ 的含义见题面，$x$ 表示 $A$ 给 $B$ 发送消息的记录区间数，$y$ 表示 $B$ 给 $A$ 发送消息的记录区间数。

接下来的 $x$ 行，每行包含两个整数 $l_{a,i}$ 和 $r_{a,i}$（$1 \le l_{a,i} \le r_{a,i} \le n$），表示 $A$ 在第 $l_{a,i}$ 天到第 $r_{a,i}$ 天（包括这两天）每天都给 $B$ 发送了消息。

接下来的 $y$ 行，每行包含两个整数 $l_{b,i}$ 和 $r_{b,i}$（$1 \le l_{b,i} \le r_{b,i} \le n$），表示 $B$ 在第 $l_{b,i}$ 天到第 $r_{b,i}$ 天（包括这两天）每天都给 $A$ 发送了消息。

保证对于所有 $1 \le i < x$，有 $r_{a,i} + 1 < l_{a,i+1}$，且对于所有 $1 \le i < y$，有 $r_{b,i} + 1 < l_{b,i+1}$。

Output Format

对于每组测试数据，输出一行一个整数，表示在第 $n$ 天结束时 $A$ 和 $B$ 之间的友谊值。

2
10 3 3 2
1 3
5 8
10 10
1 8
10 10
5 3 1 1
1 2
4 5

3
0

Hint

对于第一个测试点，用户 $A$ 和 $B$ 在第 $1$、$2$、$3$、$5$、$6$、$7$、$8$ 和第 $10$ 天互相发送了消息。由于 $m=3$，他们的友谊值会在第 $3$ 天、第 $7$ 天和第 $8$ 天分别增加 $1$。所以答案是 $3$。

由 ChatGPT 5 翻译