题目描述

旅途中，小 D 住进了一间装有环形灯带的房间。睡觉前，他发现遥控器出了故障：每次操作都会同时切换连续的几盏灯。小 D 想用尽量少的操作把所有灯关掉。

灯带上共有 $n$ 盏灯，沿顺时针方向依次编号为 $0,1,\ldots,n-1$。其中，编号为 $n-1$ 的灯的下一盏是编号为 $0$ 的灯。

每次操作，小 D 可以任选一个编号 $p$，同时切换从 $p$ 开始、沿顺时针方向连续的恰好 $k$ 盏灯的状态，所选区间可以跨过圆环首尾。也就是说，编号为 $p,(p+1)\bmod n,\ldots,(p+k-1)\bmod n$ 的灯都会改变状态：亮灯变为灭灯，灭灯变为亮灯。不同操作可以选择相同的起点。

初始亮着的灯由 $m$ 个区间描述。第 $i$ 个区间为 $[l_i,r_i)$，表示编号满足 $l_i\le j<r_i$ 的灯 $j$ 初始亮着，包含左端点，不包含右端点。其余灯初始均为灭灯。给出的区间按位置递增排列，彼此不重叠，但允许相邻区间首尾相接。

请你求出将所有灯变为灭灯所需的最少操作次数。如果无论如何都不能把所有灯关掉，输出 $-1$。

输入格式

从标准输入读入数据。

第一行包含一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行包含三个整数 $n,k,m$，分别表示灯的数量、每次操作切换的灯的数量，以及描述初始亮灯的区间数量。
• 接下来 $m$ 行，第 $i$ 行包含两个整数 $l_i,r_i$，表示区间 $[l_i,r_i)$。

输出格式

输出到标准输出。

对于每组测试数据，输出一行一个整数，表示最少操作次数；如果无解，输出 $-1$。

5
6 2 2
0 1
2 5
5 2 2
0 1
2 4
4 3 2
0 1
2 3
6 2 1
0 6
7 3 2
1 3
3 4

3
-1
2
3
1

提示

样例 1 解释

1. 第一组数据中，可以依次选择 $0,1,3$ 为起点进行操作，将所有灯关掉。最少需要 $3$ 次操作。
2. 第二组数据中，初始有 $3$ 盏亮灯。每次切换 $2$ 盏灯，亮灯数量的奇偶性不会改变，因此无法把所有灯关掉。
3. 第三组数据中，可以依次选择 $1,3$ 为起点进行操作。第二次操作会切换编号为 $3,0,1$ 的灯。
4. 第四组数据中，所有灯初始均为亮灯。分别以 $0,2,4$ 为起点操作即可。
5. 第五组数据中，两个给定区间首尾相接，初始亮灯的编号为 $1,2,3$。以 $1$ 为起点操作一次即可。

该样例同时保存在题目附件中的 lights/lights1.in 与 lights/lights1.ans 中。

样例 2

见题目附件中的 lights/lights2.in 与 lights/lights2.ans。该样例满足特殊性质 B。

样例 3

见题目附件中的 lights/lights3.in 与 lights/lights3.ans。该样例满足特殊性质 C。

样例 4

见题目附件中的 lights/lights4.in 与 lights/lights4.ans。该样例满足全部数据的约束条件，不保证满足任何特殊性质。

数据范围与测试点

对于全部数据，保证：

• $1\le T\le 10^5$；
• $2\le n\le 10^9$，$1\le k<n$；
• $1\le m\le 2\times10^5$；
• $0\le l_i<r_i\le n$；
• 对于 $1\le i<m$，有 $r_i\le l_{i+1}$；
• 每个输入文件中，所有测试数据的 $m$ 之和不超过 $2\times10^5$。

本题共有 $25$ 个测试点，每个测试点 $4$ 分，各测试点独立计分。详细数据范围见下表。

特殊性质 A：每个输入文件中，所有测试数据的 $n$ 之和不超过 $2\times10^5$。

特殊性质 B：$\gcd(n,k)=1$。

特殊性质 C：$k\mid n$，即 $n$ 是 $k$ 的整数倍。