跳跃游戏

兔子跳跃

题目描述

兔子常常感到孤独，所以当他们决定出去走走，去见见他们的朋友，他们跳得很快。

兔子正走在一条无限长的直线道路上。这条道路上点的编号为$\ldots$，$-3$，$-2$，$-1$，$0$，$1$，$2$，$3$，$\ldots$从西到东。

兔子的家是在$0$点上，而她想要见的朋友在点$1000000001$。

她是兔子当然只能通过移动跳跃前行，她有两个跳跃类型：小跳和大跳。

当她在点$x$，通过一小跳，她可以移动到点$(x+2)$或$(x-2)$。

通过一个大跳跃，她可以移动到点$(x+k)$或点$(x-k)$。

不幸的是，道路总是那么坑坑洼洼，洞的大小不一，有些还可能包含连续几个点，兔子不能跳到这些洞中。

兔子喜欢用小跳，因为这样更加的省力。请问到达$1000000001$所要使用的最少的大跳跃数量。如果不能达到这一点，输出$-1$。

注意，道路无限长，当然能跳到超过$1000000001$的点。

输入格式

有多组测试数据：

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

每组测试数据，第一行一个整数$n$，表示共有$n$个洞。

接下来一行$n \times 2$个整数，每个洞的两个端点编号，所有端点都是严格递增顺序给出（编号在$[1,10^{9}]$范围内）。

最后一行一个整数$k$。

输出格式

共$T$行，到达目标所需的最少大跳跃次数。无法到达输出$-1$。

数据范围与提示

对于$100\%$的数据，$1 \leq T \leq 10$，$1 \leq n \leq 25$，$k \in [3,10^{9}]$。

样例

5
1
1 2
3
1
1 2
4
1
2 3
3
4
2 17 21 36 40 55 59 74
19
12
187640193 187640493 187640738 187640845 564588641 564588679 564588696 564588907 605671187 605671278 605671288 605671386 755723729 755723774 755723880 755723920 795077469 795077625 795077851 795078039 945654724 945654815 945655107 945655323
475

1
-1
3
5
9